Quantum Algorithm Zoo 是现在已知的可超越经典算法的高速量子算法集。

该算法集对研究者研究量子算法提供了很好的指导参考。感谢科学家 Stephen Jordan 为科研工作者们提供重要的研究资料，并独家授权量子客（Qtumist）整理中文发布。

读者在未获得授权之前，请勿将本文任何图文内容转发或复制其中部分去其他地方。

非常感谢以下量子技术科研工作者为本文的翻译整理做出贡献（排名不分先后）：

吁超华、潘世杰、陈业红、刘勤、陈思怡、李容基、刘莹、王易之、

张安琪、段博佳、王旭南、陈希、丁齐鸣、孟则霖、孙亚鹏。

特别感谢王流伍与段博佳参与发起该项目，吁超华对本文授权的获取以及翻译内容的最终校稿，并感谢孟则霖对参考文献的梳理上传。是他们的耐心且细致的贡献，才使得该项目顺利上线，并建立长久联系。

由于翻译中难免疏漏，有不周的地方，恳请留言指正，转载请致邮（Support#Qtumist.com，把#改为@）。

更新记录：

2021年1月: 王新文博士更正公式。

其他语言参考：

English : https://quantumalgorithmzoo.org/ 中文 :  https://www.qtumist.com/quantum-algorithm-zoo/ 日本语 :   https://www.qmedia.jp/al​​gebraic-number-theoretic-algorithms/

加速：超多项式描述：给定一个$n$比特整数，求该整数质因数分解。Peter Shor提出了一个可在$\widetilde{O}(n^3)$时间内求解这个问题的量子算法 [82,125] 。用于整数因子分解的已知最快的经典算法是一般数域筛法，其算法复杂度为$2^{\widetilde{O}(n^{1/3})}$。整数因子分解算法的最优上界为$O(2^{n/4 + o(1)})$，且由Pollard-Strassen算法 [252,362] 严格证明。Shor算法攻破了RSA公钥加密算法，而与之密切相关的离散对数量子算法攻破了DSA和ECDSA数字签名方案以及Diffie-Hellman密钥交换协议。对于在密码学中广泛使用的半素数因子分解的特殊情况，文献 [271] 给出了一种比Shor算法更快的量子算法。如果存在小因数，Shor算法可以被更快的量子算法 [366] 击败，该算法使用Grover搜索算法来加速椭圆曲线因子分解。Shor算法的其他优化版本见文献 [384,386] 。还有一些经典公钥密码体制被认为不可被量子算法破解 [248] 。Shor算法的核心是周期查找，可以归约为阿贝尔隐子群问题，该问题可由量子傅立叶变换求解。许多其他一些问题可以被规约为整数分解，包括奇周期域上的矩阵群的隶属度问题 [253] ，以及与量子电路合成有关的某些丢番图问题 [254] 。

加速：超多项式描述：给定$n$比特整数$a$, $b$以及$N$，且对某个$s$，有$b=a^s\mod \ N$，求$s$。Shor在文献 [82] 给出了相应的量子算法，表明该任务可在量子计算机上以$poly(n)$时间完成。已知最快的经典算法需要$n$的超多项式时间，量子计算机可以通过与 [82] 相似的技术，解决椭圆曲线上的离散对数问题，从而攻破椭圆曲线密码 [109,14] 。 [385] 中给出了Shor算法的进一步优化。超多项式量子加速也被扩展到到半群上的离散对数问题 [203,204] 。更多内容参见阿贝尔隐藏子群。

加速：超多项式描述：给定一个正的非平方数$d$，佩尔方程为$x^2 – d y^2 = 1$。对于任意这样的$d$，该方程的解有无限多对整数对$(x,y)$。令$(x_1,y_1)$是使$x +y\sqrt{d}$值最小的一对。如果d是一个$n$比特整数（即$0\leq d < 2^n$），写出$(x_1,y_1)$一般来说可能需要指数多个比特。因此，在多项式时间内，一般是不可能找到$(x_1,y_1)$的。令$R = log(x_1+y_1 \sqrt{d})$，$\lfloor R \rceil$唯一地标识$(x_1,y_1)$。如Hallgren在文献 [49] 中所示，给定一个$n$比特数$d$，量子计算机可以在$poly(n)$时间内找到$\lfloor R \rceil$。对于这个问题，目前尚未找到多项式时间的经典算法。整数分解可以归约为这个问题。Hallgren的算法 [49] 攻破了Buchman-Williams密码体制。更多内容参见阿贝尔隐藏子群。

加速：超多项式描述：给定一个$n$比特整数$d$和环$\mathbb{Z}[\sqrt{d}]$上的一个可逆理想$I$。如果存在$\alpha \in \mathbb{Q}(\sqrt{d})$使得$I = \alpha \mathbb{Z}[\sqrt{d}]$，则$I$是一个主理想。$\alpha$可能是$d$上的指数大，因此$\alpha$一般甚至不能在多项式时间写下来。然而，$⌊log\ \alpha⌉$唯一地确定$\alpha$。我们的任务是确定$I$是否为主理想，如果是的话求出$⌊log \ \alpha⌉$。如Hallgren所示，该任务可在量子计算机上以多项式时间完成 [49] 。文献 [131] 提出了一种使用更少量子比特的改进量子算法。随后，对于任意次数的数域中主理想问题，文献 [329] 中给出了一个复杂度为次数多项式级的量子算法。整数因子分解可归约为求解佩尔方程，而求解佩尔方程可规约为主理想问题。这意味着这，主理想问题至少与整数因子分解一样困难，因此可能不属于P问题。更多内容参见阿贝尔隐藏子群。

加速：超多项式描述：如果域$\mathbb{Q}(\theta)$中以$\theta$为根的多项式的最低次数为$d$，称该数域的次数为$d$。$\mathbb{Q}(\theta)$中，那些作为$\mathbb{Z}[x]$中首一多项式的根的元素记为集合$\mathcal{O}$，且构成一个环，称为$\mathbb{Q}(\theta)$的整数环。环$\mathcal{O}$中的单位元(可逆元素)构成一个群$\mathcal{O}^*$。由Hallgren [50] 以及Schmidt和Vollmer [116] 独立研究指出，对于任意固定次数且给定$\theta$描述的$\mathbb{Q}(\theta)$，量子计算机可在多项式时间内找到$\mathcal{O}^*$的一组生成元。目前尚未有多项式时间求解该问题的经典算法。Hallgren和他的合作者随后发现了如何在次数上实现多项式的缩放 [213] 。结果同样可见文献 [329] 。这些算法依赖于求解实数加群上的阿贝尔隐子群问题。

加速：超多项式描述：如果域$\mathbb{Q}(\theta)$中以$theta$为根的多项式的最低次数为$d$，称该数域的次数为$d$。$\mathbb{Q}(\theta)$中，那些作为$\mathbb{Z}[x]$中首一多项式的根的元素记为集合$\mathcal{O}$，且构成一个环，称为$\mathbb{Q}(\theta)$的整数环。对于一个环，理想模素理想之后组成一个群，成为类群。Hallgren在文献 [50] 中指出，在给定$\theta$描述下，量子计算机可在$poly(log(|\mathcal{O}|))$时间内找出常数次数域中整数环的类群的一组生产元。随后，一个时间复杂度为$poly(d)$的改进量子算法被提出 [329] 。目前尚未有多项式时间求解该问题的经典算法。更多内容参见阿贝尔隐藏子群。

加速：超多项式描述：令$\mathbb{F}_q$为一个有限域。$\mathbb{F}_q$中所有非零元素构成一个乘法群$\mathbb{F}_q^{\times}$，而所有元素构成一个加法群$\mathbb{F}_q^{+}$（为阿贝尔群但不必须为循环群）。我们可以选择$\mathbb{F}_q^{\times}$和$\mathbb{F}_q^{+}$中的某个特征，分别记为$\chi^{\times}$和$\chi^{+}$。相应的高斯和定义为这些特征的内积：$\sum_{x\neq 0 \in \mathbb{F}_q}\chi^{+}(x) \chi^{\times} (x)$。正如van Dam和Seroussi在文献 [90] 中所指出的，量子计算机可在多项式时间内估计高斯和至多项式精度。尽管一个有限环在乘法运算下不能构成一个群，但是其单位元可以构成。通过选择一个有限环的加法群的一个表示，以及选择环中零元构成的乘法群的一个表示，可以获得该环的零元上的一个高斯和。这些高斯和也能够在量子计算机上在多项式时间内被估计至多项式精度 [90] 。目前尚未有多项式时间估计高斯和的经典算法。离散对数可以规约到高斯和估计 [90] 。通过一个和高斯和估计相关的量子算法 [47] ，Potts模型中某些特定的配分函数（partition functions）可在多项式时间被计算出来。

加速：多项式描述：给定$a,b,c,f,g \in \mathbb{F}_q$， 我们必须找出整数$x$和$y$使得$af^x+bg^y=c$。文献 [111] 指出，量子计算机可在$\widetilde{O}(q^{3/8})$时间内解决该问题，而最好的经典算法需要$\widetilde{O}(q^{9/8})$时间。文献 [111] 中的算法基于离散对数和搜索的量子算法。

加速：超多项式描述：在一组合适的基下，有限群以及紧线性群(compact linear groups)的所有表示可以表达为酉矩阵。通过量子傅里叶变换电路结合一个群的常规表示产生该群的不可约表示的一个直和。因此，对称群上的高效量子傅里叶变换 [196] ，结合hadamard测试（Hadamard test），生成一个快速的量子算法，该算法能够可加地近似$S_n$的任意不可约表示的矩阵的单个元素。类似地，利用量子Schur变换 [197] ，我们可以高效的近似$S_n$的多项式加权不可约表示的矩阵元素。文献文献 [106] 给出高效的量子电路，可以直接实现群$U(n)$、$SU(n)$、$SO(n)$和$A_n$的单个不可约表。文献 [106] 还识别出经典算法指数级困难解决的例子。

加速：多项式描述：给定三个$n\times n$矩阵$A$，$B$和$C$，矩阵乘积验证问题就是确定$AB=C$是否成立。尽管矩阵乘积计算的最好经典算法的时间复杂度$O(n^{2.373})$，解决矩阵乘积验证问题的最好经典算法的时间复杂度为$O(n^2)$。Ambainis 等人发现了一个可在$O(n^{7/4})$时间内解决此问题的量子算法 [6] 。之后，Buhrman 和 Spalek又进行了进一步的改进，提出了可在$O(n^{5/3})$时内解决此问题的量子算法 [19] 。后者的算法是基于文献 [85] 所证明的量子行走相关结论。

加速：多项式时间描述：给定一系列整数$x_1,\cdots,x_n$和一个目标整数$s$，子集求和问题就是确定是否存在该整数序列的某个子集使得子集所有元素累加起来等于$s$。这是一个NPC问题，因此无论是经典还是量子都找不到最差情况下多项式时间可解决的算法。对于计算困难的问题实例，给定的整数大小为$O(2^n)$。文献 [178] 提出一个求解该问题的量子算法，该算法的时间复杂度为$ 2^{0.241n}$，外加一些多项式因子。通过利用Ambainis的求解元素唯一性问题的量子行走算法的变种 [7] ，该算法加速由Howgrave-Graham和Joux提出的一个稍复杂的求解子集求和问题的经典算法。目前最快的子集求和的经典算法的时间复杂度为$2^{0.291n}$外加多项式因子。

加速：可变的描述：通过存储冗余数据，经典的误差纠错码可以检测和纠正比特翻转错误。对于任意线性码，最大似然解码在最坏的情况下是NPC的，但是对于结构码，已经存在有界的误差高效解码算法。目前已经有相应的量子算法加速卷积编码 [238] 和极长码 [238] 的解码过程。

加速：多项式描述：约束满足问题在计算机科学中普遍存在，且它们中的很多都是NP-hard问题，一个经典例子就是3-SAT问题。如果想满足尽量多的条件，而非全部条件，约束满足问题就变成了一个组合优化问题。（参见绝热(adiabatic)算法）利用Grover的算法可以对约束满足问题的蛮力求解方案进行平方加速。然而，求解大多数约束满足问题的典型算法，尽管仍然需要指数时间复杂度，但比检查所有解的蛮力求解方案已经具有二次加速。尽管如此，针对3-SAT问题，文献 [133] 给出一个相对最好经典算法的量子加速。对于其他约束满足问题，文献 [134,298] 也给出了多项式时间的量子加速。最常用的约束满足经典算法是回溯法，且对于某些约束满足问题该算法是已知最快的。文献 [264] 给出了回溯法的一个一般量子加速。

加速：可变的描述：众所周知，Shor的整数因子分解和离散对数算法 [82,125] 完全破解了RSA和Diffie-Hellman密码系统，以及他们的基于椭圆曲线的变体 [109,14] . (一些 “后量子”公钥密码系统已经被提出来以取代那些不知道是否会被量子攻击破坏的基础技术)。 除了Shor的算法，攻击密码系统的量子算法仍然在逐渐增长。这些算法一般分成三大类。第一类量子算法提供多项式或次指数时间算法，在标准假设前提下攻击密码系统。特别地，Childs、Jao和Soukharev所提的寻找椭圆曲线等值线的算法 [283] ，攻破了某些基于椭圆曲线的次指数时间的密码系统，而Shor算法并未攻破这些系统。第二类的量子算法通过使用Grover搜索和量子碰撞查找(Quantum collision finding )等技术，加速经典密码分析攻击算法的一部分，从相对经典攻击具有多项式加速。这些攻击针对私钥 [284,285,288,315,316] 和公钥 [262,287] ，不会使得相关密码系统不可使用，但可能会影响它们选择密钥长度。第三类量子算法利用量子叠加查询攻击块密码。这些攻击在很多情况下完全攻破了密码原语 [286,289,290,291,292] 。然而，在大多数实际情况下这样的叠加查询不可能实现。

加速：多项式描述：我们给定一个允许有$N$个输入的oracle。对于一个输入$w$（“获胜者”），相应的输出是1，而对于所有其他输入，相应的输出是0。我们的任务是找出$w$。在经典计算机上，完成该任务需要查询$\Omega ( N )$次Oracle。Lov Grover提出的量子算法 [48] 只用$O( {\sqrt N } )$次查询即能实现该任务，且被证明是最优的 [216] 。此算法随后被推广到搜索多个“获胜者” [15] 、评估任一函数的和 [15,16,73] 、找到任意函数的全局最小值 [35,75,255] 、利用不同初态 [100] 或非均匀先验概率 [123] 、使用对不同输入允许时间不同的量子Oracle [138] 、近似定积分 [77] 、以及收敛到不动点 [208,209] 。Grover算法的推广称为幅度放大 [17] ，是现如今量子算法中的一个重要的原语。幅度放大是已知与碰撞查找和图形性质相关的量子算法的核心。Grover搜索的一个自然应用是加速求解诸如3-SAT之类的NP-完全问题。该加速过程是非平凡的，因为3-SAT的最佳经典算法并非穷举搜索。然而，幅度放大相比最好的3-SAT经典算法具有二次量子加速 [133] 。文献 [134 ] 给出了其它约束满足问题的二次加速。Grover搜索和幅度放大的进一步应用的例子参见文献 [261,262] 。与Grover搜索密切相关，但比Grover搜索更难的问题是空间搜索，其中数据库查询受限于某些图形结构。对于充分连通的图，$O(\sqrt{N})$量子查询复杂度仍然可实现 [274,275,303, 304, 305, 306, 330] 。

加速：超多项式描述：令$G$是一个有限生成的Abeli-群，并令$H$是$G$的某个子群，并使得$G/H$是有限的。设$f$是$G$上的一个函数，使得对于任意${g_1},{g_2} \in G$，$f(g_1) = f(g_2)$成立当且仅当$g_1$和${g_2}$在$H$的同一个陪集内。我们的任务是通过查询$f$找出$H$（即找出$H$的一组生成元）。量子计算机解决此问题需要使用$O(log (| G |))$次查询，而经典计算机需要$\Omega (| G |)$次。该算法的一般情况由Boneh和LiPton首次公式化 [14] 。然而，很好的抽象化该算法是较为困难的，因为如文献 [76] 第5章所述，它包含许多历史上许多重要的量子算法并作为该算法的特例，包括Simon算法 [108] 。Simon算法激发了整数因子分解和离散对数算法的核心—Shor周期查找算法。阿贝尔隐子群算法也是佩尔方程、主理想、单位群和类群算法的核心。在某些情况下，解决阿贝尔隐子群问题可只用单个查询而非$log (| G |)$次 [30] 。周期查找问题中通常假设函数$f(x) \ne f(y)$，除非$x – y = s$，其中$s$是周期。当该限制放松时，文献 [388] 给出了一个相应的量子算法。文献 [389] 将周期查找推广到适用于一些特殊的Oracles，这些Oracles只提供关于函数少数几个最重要比特。

加速：超多项式描述：令$G$是一个有限生成群，并令$H$是$G$的一个子群，且$H$具有有限多个左陪集。令$f$是$G$上的一个函数，使得对于任何${g_1},{g_2}$，$f({g_1}) = f({g_2})$当且仅当${g_1}$和${g_2}$位于$H$的相同左陪集时成立。我们的任务是通过查询$f$找出$H$ (即找出$H$的一组生成元)。量子计算机解决此问题需要使用$O(log (| G |))$次查询，而经典计算机需要$\Omega (| G |)$次 [37,51] 。然而，这不能作为有效的量子算法，因为一般来说，处理从这些查询中获得的量子态可能需要指数时间。对于某些特定的非阿贝尔群 [81,55,72,53,9,22,56,71,57,43,44,28,126,207,273] ，已有高效的针对隐子群问题的量子算法。文献 [69] 给出了一个略显过时的综述。特别令人感兴趣的是对称群和二面体群，其中对称群的解可以解决图同构问题，而二面体群的解可解决某些格问题 [78] 。尽管做出许多努力，除了一些特殊情况 [312] ，尚未有针对这些群的多项式时间的解。然而，Kuperberg发现了一个时间复杂度为$2^{O(\sqrt {log \ N} )}$的算法 [66] ，用于寻找二面体群${D_N}$的一个隐藏子群。ReGeV随后改进了该算法，使得它不仅使用次指数时间，还使用多项式空间 [79] 。文献 [218] 对此进一步改进，需要所需量子比特数渐近规模的时间。文献 [311] 中给出了置换集下函数同构测试的一些更一般的问题的量子查询加速（尽管按照门计数不一定是高效的量子算法）。

加速：多项式（直接），超多项式（递归）描述：我们给定了一个Oracle，其输入为$n$比特，输出为$1$比特。给定输入$x \in \{{ 0,1\}} ^n$，输出是$x\odot h$，其中$h$是$n$比特“隐藏”字符串，而$\odot$表示按比特的内积模2。我们的任务是找出$h$。在经典的计算机上，这需要$n$次查询。如Bernstein和Vazirani在文献 [11] ，该任务在量子计算机上使用一次查询就能实现。此外，人们可以构造这个问题的递归版本，称为递归傅立叶采样（recursive Fourier sampling），使得量子计算机比经典计算机需要指数级少的查询次数 [11] 。了解量子电路的量子加速普遍性的相关工作可参见文献 [256,257] ，以及了解有关检测oracle函数与另一oracle函数的傅立叶变换之间的相关性的量子查询加速相关工作可参见文献 [258,270] 。

加速：P上指数加速， BPP上无加速描述：我们给定了一个Oracle，其输入为$n$比特，输出为$1$比特。我们承诺，在$2^n$可能的输入中，要么全部，要么没有，要么一半输出1。我们的任务是将平衡情况（一半输入输出1）与恒定情况区分开来（全部输入输出1或没有一个输入输出1）。Deutsch在文献 [32] 中表明，对于$n＝1$，量子计算机用一次查询即可实现该任务，而任何确定的经典算法都需要两次查询。这是历史上第一个定义明确的实现对经典计算加速的量子算法。（文献 [259] 给出了一个相关的、较新的教学实例。）Deutsch和Jozsa在文献 [33] 中发展了针对任意$n$的单次查询量子算法。虽然在概率上使用$O( 1 )$查询容易解决Deutsch-Jozsa问题，但该问题最坏情况在经典上具有指数级确定性查询复杂度。

加速：多项式描述：若布尔表达式每个变量仅使用一次，该表达式即称为公式。每个公式对应一个无扇出(fanout)的电路，因此具有树型拓扑结构。根据Reichardt 张成方案形式体系（Span program formalism），任意对$N$个变量有$O(1)$扇入的公式的量子查询复杂度为$\Theta(\sqrt{N})$ [158] 。该结果是一系列工作 [27,8,80,159,160] 之后的最佳结果。这些工作由Farhi等人发起，他们发现运用持续量子行走对$O(2^n)$个变量的NAND树求值的时间复杂度为$O(2^{0.5n})$ [38] ，而用经典计算机则需$\Omega(2^{0.753n})$的时间。在许多情况下，量子公式求值在查询复杂度和时间复杂度上均高效。张成方案形式体系也能够产生量子查询复杂度下界 [149] 。从某角度来看，Grover算法可以认为是任意门均为OR的公式求值的一个特例。目前人们也对计算非布尔公式的量子复杂度展开研究 [29] ，但尚未完全成熟。Child等人扩展到输入变量可能重复的情况（即电路第一层可能包含扇出） [101] 。他们提出一个使用$O(min\{{N,\sqrt{S},N^{1/2}G^{1/4}\}})$次查询的量子算法，其中$N$是可重复输入变量个数，$S$是输入变量的重数，$G$是公式中门的个数。文献 [164,165,269] 考虑NAND树问题的一些特例，其中采用不等输入NAND门的数目受限。其中的某些特例产生量子和经典查询复杂度之间的超多项式分离（separation）。

加速：多项式描述：假设已有Oracle计算平滑某个函数$f:\mathbb{R}^d\mapsto \mathbb{R}$。Oracle中对$f$的输入输出的精度误差是有限的。我们的任务是估计$\nabla f$在某些特殊点$\mathbf{x}_0\in \mathbb{R}^d$的值。文献 [61] 指出，量子计算机能够运用一次查询即可完成该任务，而经典计算机则需要$d+1$次。Bulger在文献 [20] 中指出该任务在求解最优化问题中潜在应用。如文献 [62] 附录D所示，量子计算机能够使用梯度算法以$O(d)$次查询找出$d$维二次型的最小值。相应的在文献 [94] 中，经典计算机则需要至少$\Omega(d^2)$次查询。文献 [147,148,223] 给出基于汉明距离找出盆地(basin)形函数最小值的单次查询的量子算法。文献 [62] 所提量子算法也可以使用$O(d)$次查询提取所有二次型的$d^2$矩阵元素，并且更一般地，使用$O(d^{n-1})$次查询提取一个$d$变量平滑函数的所有$d^n$个$n$阶导数。文献 [130,146] 指出，有限域内$d$个变量的二次型和多线性多项式可能可以少于经典$d$个量子查询的复杂度提取。

加速：超多项式描述：现有oracle实现$\mathbb{Z}_n$上的某个函数$f$。已知$f(x)=g(x+s)$，其中$g$是已知函数，$s$是未知移位。隐藏移位问题就是找出$s$。通过Grover问题规约到该问题，很明显可看出至少需要$O(\sqrt{N})$次查询来解决隐藏移位问题。但是在某些情况下的隐藏移位问题只需使用$O(1)$查询。特别地，Van Dam等人指出，如果$f$是一个环或域上的乘法特征，该查询复杂度可达到cite{89}。之前发现移位的Legendre符号算法 [88,86] 也在此类情况中，因为Legendre符号$(\frac{x}{p})$是$\mathbb{F}_p$上的一个乘法特征。对此类问题，目前没有时间复杂度为$O(polylog(N))$的经典算法。更进一步地，在给定生成器量子查询的能力下，解决移位Legendre符号问题的量子算法可攻破密码伪随机生成器 [89] 。文献 [312] 中给出了差集(difference set)隐藏移位问题的量子加速，并且这也包含了Legendre符号问题这个特例。Roetteler在文献 [105,130] 中指出求解某种非线性Boolean函数隐藏移位的量子指数级加速。基于此工作，Gavinsky，Roetteler和Roland在文献 [142] 中指出，对随机布尔函数$f:\mathbb{Z}_2^n\mapsto \mathbb{Z}_2$的隐藏移位问题有平均$O(n)$的量子复杂度，而其经典查询复杂度为$\Omega(2^{n/2})$。在文献 [143] 中，尽管他们是用二面群的隐子群问题来描述，但蕴含了$\mathbb{Z}_N$上单射函数隐移位问题的量子查询复杂度为$O(log \ n)$，而经典查询复杂度为$\Theta(\sqrt{N})$。对于$\mathbb{Z}_N$上单射函数隐移位问题，Kuperberg的筛分算法 [66] 给出了目前最好的量子电路复杂度$O(2^{C\sqrt{log \ N}})$。

加速：可变的描述：令$p(x)=a_dx^d+\cdots+a_1x+a_0$是有限域$GF(q)$上的一个多项式。给定一个Oracle实现给定输入$x\in GF(q)$，输出$p(x)$。多项式重构(reconstruction)问题是指通过查询Oracle确定系数$a_d,cdots,a_0$。对经典计算机而言，$d+1$次查询是必要且充分的。（一些文献用重构而非插值）。对量子计算机而言，$d/2+1/2$次查询是必要的，而$d/2+1$次查询是充分的 [360,361] 。$d$次$n$元多项式插入问题的经典查询复杂度为${n+d}\choose d$。文献 [387] 指出，在$\mathbb{R}$和$C$上的量子查询复杂度为$\frac{1}{n+1}\binom{n+d}{d}$，且在$\mathbb{F}_q$（$q$足够大）上的复杂度为$\frac{d}{n+d}\binom{n+d}{d}$。针对oracle输出为$\chi(f(x))$[390] ，其中$\chi$是$GF(q)$的二次特征，以及oracle输出$f(x)^e$的情况，也存在相应的量子算法 [392] 。这些算法推广了隐藏移位算法 [89] ，并相对经典计算具有指数级加速。在给定受噪声影响且不完全的访问函数值的oracle下，文献 [391] 给出一个重构有限域有理数函数的量子算法。

加速：超多项式描述：给定一个长度为$n$的字符串$T$和一个长度为$m(m < n)$的字符串$P$，且两者均来自相同的字母集。模式匹配问题就是找出$T$的一个子字符串$P$或者报告$P$不是$T$的子字符串。更一般的，$T$和$P$可能是$d$维数组而非一维数组（即字符串）。接着模式匹配给出$P$作为$m\times m\times \dots \times m$块在$n\times n \times \dots \times n$数组$T$中的位置或者返回没有这样位置的报告。非结构化搜索 [216] 给出的$\Omega(\sqrt{N})$搜索下界蕴含着此类问题最坏情况下的量子搜素复杂度为$\sqrt{n}+\sqrt{m}$。文献 [217] 给出一个量子算法能达到该复杂度，外加一些对数因子。这个量子算法利用了Grover算法和一个经典确定性采用算法。近期，Montanaro证明了，当$m$大于$log(n)$，模式匹配的平均情况下能够实现超多项式量子加速。具体来说，文献 [215] 给出的量子算法以时间复杂度$\widetilde{O}((n/m)^{d/2}2^{O(d^{3/2}\sqrt{log \  m})})$解决平均情况下的模式匹配。该量子算法是通过扩展针对二面隐藏子群和隐藏移位问题的Kuperberg量子筛分算法 [66] 构建而成。因此，该算法能够在$d$维下运行，并能允许少量噪声，且经典上将模式匹配问题规约到隐藏移位的带噪声$d$维版本。

加速：超多项式描述：我们给出对$n\times n$的矩阵$A$的oracle访问和向量$b$的一些描述。希望对一些可有效计算函数$f$，能找到$f(A)b$的一些性质。假设$A$是一个Hermitian矩阵，每行有一个$O(polylog \  n) $非零元素，条件数为$k$。如文献 [104] 所示，量子计算机可以在$O({k}^{2}log \ n)$时间内以多项式精度计算关于向量$f(A)b$的各种算符期望值(假设等比例于向量$b$的量子态与是可有效制备的)。对于某些函数，如$f(x)=1/x$，这个过程可以扩展到非Hermitian甚至非方阵$A$。随后，此算法的运行时间，在文献 [138] 中提升到$O(k\ {log}^{3}\ k\ log\ n) $，在文献 [263] 中得到了关于精度的指数级改进。该量子算法的扩展已经应用于估计电磁散射截面 [249] （另见文献 [369] 的不同方法），求解线性微分方程 [156,296] ，估算网络电阻 [210] ，最小二乘曲线拟合 [169] ，求解Toeplitz系统 [297] ，和机器学习 [ 214,222,250,251,309] 等问题。 文献 [246] 很好地总结了基于线性系统的量子机器学习算法的一些局限性。文献 [220] 指出，量子计算机可以仅用$O(log \ n) $量子比特就能对良态的$n\times n$矩阵求逆，而最佳经典算法要用$O({log}^{2}n)$比特。文献 [279] 给出了该量子算法的后续改进。

加速：常数描述：假设我们给定访问一个含有$N$个数的升序列表的Oracle。给定一个数$x$，我们的任务是从列表中找到元素$x$的位置。在经典中，可能最好的算法是二分查找，它需要$log_2 N$次查询。Farhi等人证明量子计算机可以使用$0.53log_2 N$次查询来实现该任务 [39] 。目前，最著名的确定量子算法解决这个问题需要$0.433log_2 N$次查询 [103] 。文献 [219,24] 已经证明解决此问题量子计算机需要查询的下届为$\frac{ln 2}{\pi} log_2 N$。在文献 [10] 中，给出了一个随机量子算法，其预期查询复杂度小于$1/3log_2 N$。

加速：多项式描述：令$G$是含有$n$个顶点的图。我们给定一个Oracle，当给定${1,2,\dots,n }$中一对整数时， 该oracle判定相应的顶点是否通过某条边连接。在以前的工作 [35，52，36] 基础上，Dürr等人 [34] 证明，寻找加权图的最小生成树，并确定有向和无向图的连通性的量子查询复杂度为$\Theta(n^{3/2})$，并且找到最低权重路径具有$O(n^{3/2}log^2 n) $量子查询复杂度。在文献 [13,272,318] 的研究之上，文献 [317] 指出判断一个图是否是二分图、检测周期、以及判断一个给定顶点是否可以从另一个顶点到达(强连通)，都可以使用$\widetilde{O}(n^{3/2})$级别的查询和量子门来实现，并且只需要对数级别的量子位。 文献 [240] 给出了一个基于张成方案的量子算法，该算法能够以$\widetilde{O}(n)$时间检测树。如果存在常数$c$，使得具有某个属性的每个图的边与顶点的比率至多为$c$，则该图属性是稀疏的。Childs和Kothari已经证明，如果稀疏图不能用一系列禁用子图特征化表示，那么它具有$\Theta(n^{2/3})$的查询复杂度，否则查询复杂度为$o(n^{2/3})$ [140] 。前者算法基于Grover搜索，后者基于量子游走 [141] 。 根据Mader定理，稀疏图属性包括所有非平凡的次封闭属性（minor-closed properties）。这些属性包括平面性，成为森林，以及不包含给定长度的路径。根据Aanderaa-Karp-Rosenberg猜想，上述问题在经典计算机上具有$\Omega(n^2) $的查询复杂度。另一个有趣的计算问题是在给定的图$G$中找到子图$H$。最简单的例子为寻找团为3的三角形问题。文献 [319] 给出了目前已知最快的三角形查找问题的量子算法，其查询复杂度为$O(n^{5/4})$，改进了文献 [276,175,171,70,152,21] 的结论。当图足够稀疏时，存在更强的量子查询复杂性上界 [319,320] 。三角形查找问题的经典查询复杂度为$\Omega(n^2) $ [21] 。更一般地，量子计算机使用$O(n^{2-2/k-t})$次查询就可以找到$k$个顶点的任意子图，其中$t=(2k-d-3)/(k(d+1)(m+2)) $，$d $为子图$H$的顶点的度， $m+d$为边数 [153] 。这改进了以前的算法 [70] 。在某些情况下，如果$G$是稀疏的， [140] 的量子算法更优，它使用$\widetilde{O}( n^{\frac{3}{2}-\frac{1}{\mathrm{vc}(H)+1}} ) $查询找到$H$，其中$vc(H) $是$H$的最小顶点覆盖的大小。文献 [241] 给出了寻找3—一致（3-uniform）超图上常数大小的子超图的量子算法，其查询复杂度为$O(n^{1.883})$。

加速：多项式描述：令$G$是一个具有$n$个顶点、$m$条边和度为$d$的图。假设我们有个oracle，当查询某顶点的标签以及某个数 $j \in {1,2,\dots,d}$时，该oracle输出该顶点的第$j$个邻居，或者如果顶点的度小于$d$，则输出为空。假设我们认定， $G$要么是二分的，要么远远不是二分的，也就是说，需要去除常数比例边数以实现二分性。如文献cite144}所证，确定二分性的量子复杂度为$\widetilde{O}(N^{1/3})$。同样在 [144] 中，证明了区分扩展图（expander graph）与远离扩展图的图具有量子复杂度$\widetilde{O}(N^{1/3})$和$\widetilde{\Omega}(N^{1/4})$，而经典复杂度是$\widetilde{\Theta}(\sqrt{N})$。其中关键的量子算法工具是Ambainis的元素差异（element distinctness）算法。文献 [34] 指出，找出最小生成树具有量子查询复杂度$\Theta(\sqrt{NM})$、判断无向图连通性具有量子查询复杂度$\Theta(N) $、判断有向图连通性的量子查询复杂度为$\widetilde{\Theta}(\sqrt{NM})$、计算加权图上的从给定源点到其他所有顶点的最短路径具有量子查询复杂度$\widetilde{\Theta}(\sqrt{NM})$。 文献 [317] 给出了对于强连通图的量子算法，判定二分性及确定图是否是森林的运行时间为$\widetilde{O}(N \sqrt{d})$并且仅使用对数级的量子比特。

加速：超多项式描述：一些计算问题可以按照通过一个迷宫所需查询复杂度重新描述。也就是说，我们有某个图$G$，且有访问该图的Oracle。当查询给定节点标签时，Oracle返回所有相邻节点的标签。现在的任务是从某个源节点（即它的标签）开始，找到某个特定标记的目标节点的标签。正如Childs等人在 [26] 中所示，至少对于某些图，量子计算机在完成该任务上比经典计算机有指数级优势。具体来说，假设通过一个随机“焊接”（weld）将两个深度为$n$的二叉树连接在一起,从而得到除了两个根之外的所有节点都具有度数为3的图。 从一个根开始，量子计算机可以经过$poly(n)$次查询找到另一个根，然而这被证明使用经典查询是不可能的。

加速：多项式描述：假如我们有一个Oracle，这个黑盒可以访问一个定义域大小为$N$的二对一函数$f$。碰撞问题就是查找满足$f( x )=f( y )$的一对$x,y\in \{{ 1,2,\dots ,N \}}$。碰撞问题的经典随机查询复杂度为$\Theta ( \sqrt{N} ) $，而Brassard等人证明量子计算机可以使用${ O}( {{N}^{{1}/{3}}} ) $次查询即可解决此问题 [18] （另请参阅 [315] ）。去除$f$是二对一函数的前提之后，问题变成元素差异问题，这个问题的经典查询复杂度为$\Theta ( N )$。通过改进 [21] ，Ambainis给出了一个解决元素差异问题的量子算法，其查询复杂度为${\mathrm O}( {{N}^{{2}/{3}}} )$，并且这个算法是最优的 [7,374] 。另外一个问题是确定是否存在$k$重碰撞，也称$k$重差异（$k$-distinctness）问题。通过改进算法 [7,154] ，解决$k$重差异问题的最好的量子算法的查询复杂度为${ O}( {{n}^{{3}/{4}-{1}/{( 4( {{2}^{k}}-1 ) )}}} )$ [172,173] 。对于$k=2,3$的情形，时间复杂度也是这样，只是外加一个对数级因子 [7] 。对于$k>3$的情形，已知最快的量子算法时间复杂度为${ O}( {{n}^{{( k-1 )}/{k}}} )$ [363] 。给定两个定义域大小分别为$N$和$M$的函数$f$和$g$， $f( x )=g( y )$的一对$x,y$被称为一个爪子。对于$N=M$情形，文献 [7] 中算法解决爪子查找问题需要${ O}( {{N}^{{2}/{3}}} )$次查询，相对于之前需要${ O}( {{N}^{{3}/{4}}}log \ N )$次查询的量子算法 [21] 有所改进。对于$N\ne M$情形，文献 [364,365] 给出了针对不同参数改进查询复杂度的进一步工作。更一般的，另一个和元素差异问题相关的问题是：在给定访问一个序列的Oracle之后，估计第$k$频率矩（$k$-th frequency moment）${{F}_{k}}=\sum_{j}{n_{j}^{k}}$，其中${{n}_{j}}$是$j$在序列中出现的次数。对于这个问题，文献 [277] 的算法给出近似二次加速。另请参阅图碰撞ref{graph collision}。

加速：多项式描述：给定一个$n$个结点的无向图，以及一个通过0或者1访问图顶点标签的Oracle。图碰撞问题就是通过基于oracle的查询，来确定是否存在一对相连顶点的标签均为$1$。我们可以把Grover无结构搜索算法看做图碰撞问题的一个实例：将星图顶点代表数据库元素，中心顶点标为$1$，其他顶点标为0。因此，这个问题的量子查询复杂度为$\Omega( \sqrt{n} )$，经典查询复杂度为$\Theta ( n )$ 。在文献 [70] 中，Magniez, Nayak, 和Szegedy提出了一个${ O}( {{N}^{{2}/{3}}} )$次查询的量子算法来解决一般图的图碰撞问题。对于一般图的图碰撞问题，该算法仍然保持最优量子查询复杂度上界。然而，对于几个特殊类别的图形，可以有更强的上界。具体来说，对于一个有$l$个非邻边(non-edges)的图$G$，量子查询复杂度为$\widetilde{{O}}( \sqrt{n}+\sqrt{l} )$ [161] ；对于最大独立集合大小为$\alpha $的图$G$，量子查询复杂度为${ O}( \sqrt{n}{{\alpha }^{{1}/{6}}} )$ [172] ；对于独立集合顶点度之和最大的为${{\alpha }^{*}}$的图$G$，量子查询复杂度为${ O}( \sqrt{n}+\sqrt{{{\alpha }^{*}}})$ [200] ；对于树的宽度为$t$的图$G$，量子查询复杂度为${ O}( \sqrt{n}{{t}^{{1}/{6}}} )$ [201] 。另外，对于每对顶点之间的边以固定概率出现的随机图（即Erdős–Rényi图）来说，量子查询复杂度以很高的概率为$\widetilde{{ O}}( \sqrt{n} )$ [200] 。可以参考文献 [201] 对于这些结果的总结，以及两类非常复杂且不便于在此描述的图的上界。

加速：多项式描述：假如我们拥有访问$k$个矩阵的oracle，且每个矩阵都是$n\times n$的。给定整数$i,j\in { 1,2,\dots ,n }$以及$x\in { 1,2,\dots ,k }$，Oracle可以返回第$x$个矩阵的$ij$元素。我们的任务是确定是否所有的$k$个矩阵是可交换的。Itakura [54] 指出，量子计算机可以用${ O}( {{k}^{{4}/{5}}}{{n}^{{9}/{5}}} )$次查询完成此任务，而经典计算机需要$\Omega ( k{{n}^{2}} )$次查询。

加速：多项式描述：给定一个群$G$的$k$个生成元的列表，以及一个实现群乘法的黑盒。通过查询这个黑盒，我们希望确定这个群是否是可交换的。已知的最好的经典算法是由Pak提出，需要${ O}( k )$次查询。Magniez 和Nayak指出该任务的量子查询复杂度为$\widetilde{\Theta }( {{k}^{{2}/{3}}} )$ [139] 。

加速：超多项式描述：任意的阿贝尔群$G$都可视为一个格（lattice）。一个群$G$的子群$H$是一个子格，且$H$的陪集是该子格的所有平移。阿贝尔隐子群问题的一般解决方法为：先获得隐子群一个随机陪集内元素的叠加态，然后对此叠加使用傅里叶变换从而对偶格（dual lattice）进行采样。我们不推广到非阿贝尔群（另请参阅 [non-Abelian hidden subgroup] ），而是推广到识别隐子集（不是网格）问题。Childs等人在 [23] 指出，对于某些由多项式定义的子集（例如球体），该问题可在量子计算机上被高效求解。Deckeret等人在文献 [31,212] 中展示了如何高效求解相关问题。

加速：多项式描述：我们给定一个Oracle，可以计算从空间$\mathbb{R}^d$到某个任意集合$s$的函数$f$的值，其中函数$f$是球对称的。我们希望以一定的精度找到其对称中心。(为了简单起见，让精度是一个固定值)。Liu [110] 给出了一种基于曲线变换的量子算法，该算法使用一个不依赖空间维度$d$的常数量量子查询来解决此问题。这构成了一个对经典下界$\Omega{d}$的多项式加速。该算法当函数$f$波动在足够小的范围内时起作用，例如，当函数$f$的度集（degree set）是足够薄的球形壳时。 量子算法一个理想化的连续模型中工作，非严格的论证表明离散化影响应该很小。

加速：超多项式描述：假设一个有限群$G$以Oracle形式按照如下方式给出。对于$G$中的每个元素，都会分配一个相应的标签。 给定一对有序的群元素标签，Oracle返回它们积的标签。 已经存在一些关于这样群体的典型困难问题。现在任务是给定的一组生成元的标签条件下，找出群的阶。另一个任务是，给定一串比特串，确定它是否对应于群中的元素。该成员（membership）问题的一个建设性版本要求，在确定为“是”的情况下，将给定元素分解为群生成元的乘积。经典上，即使$G$是阿贝尔群，这些问题也不能用$polylog(|G|)$次查询来解决。对于阿贝尔群，Mosca在文献 [74] 中指出，通过把问题归约为阿贝尔隐子群问题，量子计算机可以使用$polylog(|G|)$次查询来解决这些问题。此外，Watrous在文献 [91] 中指出，对任意的可解群，量子计算机可以使用$polylog(|G|)$查询来解决这些问题。 对于在有限域上以矩阵而非Oracle形式给出的群，找群阶问题和成员问题可以使用离散对数和整数因子分解的量子算法 [124] 以多项式时间解决。参考群同构算法。

加速：超多项式描述：令$G$是一个有限群。 给$G$的每个元素都分配了一个任意的标签(比特串)。 给定一对有序的群元素标签，群Oracle会返回其积的标签。给定两个群 和 的Oracle的访问方式，以及每个群的生成元，我们必须判定$G$和$G’$是否同构。 对于阿贝尔群，我们可以通过使用文献 [127] 中给出的量子算法以$poly(log(|G|), log(|G’|))$次Oracle查询解决此问题。该算法将任意一个阿贝尔群分解成环群（cyclic group）的直积。对于某特定类的非阿贝尔群，文献 [128] 所提出的量子算法使用$poly(log(|G|), log(|G’|))$次Oracle查询来解决群同构问题。具体地说，如果一个群$G$有一个正规阿贝尔子群$A$，以及一个阶与$|A|$互素的元素$y$，且满足$G= A,y$。 Zatloukal [202] 最近对一个与群同构密切相关的问题—群扩张等价性测试问题给出了指数量子加速的解决方法。

加速：多项式描述：假设我们有两个黑盒$A$和$B$，它们的定义域是整数1到$T$，值域是整数1到$N$。以均匀分布的方式随机选择输入，得到可能输出的概率分布。我们希望以常数精度近似由$A$和$B$确定的概率分布之间的$L_1$范数距离。经典算法中，所需的查询次数本质上与$N$呈线性关系。 如文献 [117] 所示，量子计算机可以使用$O(\sqrt{N})$次查询来实现。概率分布的近似均匀性和正交性也可以在量子计算机上用 $O(N^{1/3})$次查询来确定。主要使用的工具是文献 [16] 中的量子计数算法。文献 [265] 给出一个针对该任务的进一步改进的量子算法。

加速：超多项式描述：对于一个不要求可交换有限环$R$，假设我们给定在该环上实现加法和乘法运算的黑盒。同时给出了$R$的一组生成元。关于加法运算，$R$构成了一个有限阿贝尔群$(R,+)$。如文献 [119] 所示，量子计算机可在$poly(log(|R|))$时间内找到一组加法生成元${h_1,\dots,h_m}\subset R$使得$(R,+)\simeq \langle h_1 \rangle\times \dots \times \langle h_M \rangle $，$m$是关于$|R|$的对数多项式大小。这使得我们可以有效计算$R$的乘法张量。如文献 [118] 所示，我们可以类似找到$R$中任意理想的加法生成集。这使得我们可以找到两个理想值的重叠、找到它们的商、证明给定的环元素是否属于一个给定的理想、证明给定的元素是否是一个单元且如果不是找出到它的逆元、找到加性和乘法单位元、计算理想的阶数、解环上的线性方程组、定理想是否最大、查找零化子（annihilator），并环同态的内射性和满射性。如文献 [120] 所示，我们也可以使用量子计算机来有效地判断一个以黑盒形式给定的有限环上的一个给定多项式是否等于零。已知解决这些问题的经典算法的时间复杂度为$poly(|R|)$。

加速：多项式描述：假设有$N$枚硬币，其中$k$枚是伪造的。真硬币的重量都是相同的，假硬币的重量也都相同的，但与真硬币重量不同。现在有一个平衡天平，可以比较任何一对硬币子集的重量。经典算法需要$\Omega  (klog (N/k  )  )$次称量，以识别所有的伪币。此时可以引入一个量子黑箱oracle，对于给定一对等基数的硬币子集，黑箱oracle可以输出一个表示天平平衡或不平衡的量子比特。基于Terhal和Smolin以前的工作 [137] ，Iwama等人表明在量子计算机上，$O(k^{1/4}  )$次查询就可以识别所有的伪币 [136] 。该研究中，量子加速的核心技术是幅度放大和Bernstein-Vazirani算法。

加速：多项式描述：假设我们可以访问一个$n\times m$矩阵$A$的(整数)项，我们希望确定矩阵的秩。经典算法需要$nm$阶的查询次数。在文献 [149] 的基础上，Belovs [150] 提出了一个量子算法，该算法在矩阵的秩至少为$r$的前提下能够实现较少的查询次数。具体来说，Belovs算法使用$O ( \sqrt{r ( n-r+1  )}LT  )$次查询，其中， $L$是$A$的$r$个最大奇异值倒数的均方根，$T$是一个依赖于矩阵稀疏性的因子。对于一般的矩阵$A$，$T=O ( \sqrt{nm}  )$。如果$A$的任何行或列中最多有$k$个非零项，则$T=O ( k \ log ( n+m  )  )$。（为了在$k$-稀疏情况下实现相应的查询复杂度，Oracle必须以列索引作为输入，并提供该列的非零矩阵元素的列表作为输出。）作为一个重要的特例，我们可以使用这些量子算法来确定一个方阵是否是奇异矩阵，这个问题有时也被称为行列式问题。对于一般的矩阵$A$，行列式问题的量子查询复杂度不低于经典的查询复杂度 [151] 。然而，在指定矩阵$A$的某些特性后，并不排除文献 [151] 能够加速的可能性，比如指定矩阵$A$的稀疏性或$A$不具有小的奇异值。

加速：多项式描述：半环是一个具有加法运算和乘法运算的集合，除了没有加法逆元，它服从环的所有公理。各种半环上的矩阵乘法有许多被应用于图问题中。半环上的矩阵乘法可以直接通过Grover在简单乘法上的改进来实现加速，从而产生一个量子算法，该算法能在$\widetilde{O} ( n^{5/2}  )$时间内实现一对$n\times n$矩阵的乘法运算。对于某些半环，该算法的性能优于已知最快的经典算法，而对于一些半环则没有 [206] 。一个有趣的特例是布尔半环，其中OR用作加法，AND用作乘法。在一般情况下，没有任何一个量子算法在求解布尔半环矩阵乘法问题上能够优于已知最好的经典算法，其计算复杂度为$n^2.373$。然而，对于稀疏输入、量子输出，量子加速是众所周知的。特别地，设$A,B$是$n\times n$布尔矩阵。令$C=AB$，且$l$是$C$的元素等于1(即真)的个数。对文献 [19,155,157] 改进后，文献 [161] 表明量子查询复杂度的最佳上界是$\widetilde{O} ( n\sqrt{l}  )$。如果输入矩阵是稀疏的，那么在一定范围内，能超越已知最快经典算法的量子算法已被提出 [206] 。有关量子算法与经典算法的详细比较，请参见文献 [155,206] 。已有量子算法可以在$\widetilde{O}(n^{2.473})$时间内执行(max，min)半环上的矩阵乘法，在$\widetilde{O}(n^{2.458} )$时间内执行距离占优半环上的矩阵乘法 [206] 。对于这两个问题，已知最快的经典算法具有$\widetilde{O}( n^{2.687} )$的复杂度。

加速：多项式描述：我们可以通过黑箱oracle访问一个函数$f:D\rightarrow R$，其中$D$和$R$是有限集。已知某些性质：$P\subset ( D\times R  )^k$，例如为显式列表。我们的任务是找到$D$中满足$P$的一个大小为$k$的子集，即$( (x_{1},f ( x_{1}  )  ),…,  (x_{k},f ( x_{k} )  ) )\in P$，如果不存在这样的子集则摒弃。通常，我们希望用最少的查询次数便可完成这样的任务。作为文献 [7] 的推广， [162] 表明这个任务可以通过$O (| D  |^{k/ ( k+1 )} ) $次量子查询来实现。作为一个显著特例，这个算法解决了$k$子集求和问题，即从一个列表中找到$k$个数，这$k$个数的和满足某个期望值。文献 [163] 证明了这个量子查询复杂度的一个匹配下界。

加速：多项式描述：通配符查找是通过查询某个Oracle $f$ 来识别隐藏的$n$比特串$x$。给定集合$S\subset \{{1,2,\dots,n\}}$以及$y\in \{{0,1\}}^{|s|}$，如果由$s$指定的$x$的子串等于$y$，则$f$返回1，否则返回0。该问题在经典上的查询复杂度为$\Theta{n}$。文献 [167] 指出，该问题的量子查询复杂度为$\Theta(\sqrt{n})$。有趣的是，该问题的二次加速并非通过幅度放大或量子行走来实现的，而是通过使用所谓的“良好测量”（Pretty Good Measurement）。该文献 [167] 还给出组合群测试相关问题量子加速。该结果以及后续更快的组测试（Group testing）量子算法在小集团测试(Junta testing)和组测试（Group testing）条目中也进行了讨论。

加速：多项式描述：网络是一个有向图，其边用表示其承载容量的数字标记，且边的两个顶点被指定为源点（source）和汇点（汇点）。网络上的流是对边的流的一个分配，使得没有流会超过边的承载容量，并且对于源点和汇点之外的每个顶点，总流入量等于总流出量。网络流问题为，在给定网络的情况下，找到能使从源点到汇点的总流量最大化的流。对于一个具有$n$顶点、$m$条边以及最大幅度为$U$的整数容量的网络，文献 [168] 给出了一个能在时间$O(min\{{n^{7/6}\sqrt{m}U^{1/3},\sqrt{nU}m\}}\times log \ n)$内找到最大流的量子算法。网络流问题与寻找图的最大匹配问题（即将每个顶点连接到至多一个其他顶点的边的最大尺寸子集）密切相关。文献 [168] 给出的算法表明，当图是二分图的情况下，寻找最大匹配的时间复杂度为$O(n\sqrt{m+n}log \ n)$，而对于一般图，时间复杂度则为$O(n^2(\sqrt{m/n}+log \  n)log \ n)$时间。这些算法的核心是Grover搜索算法。由于不同的参数方案倾向于选择不同的经典算法，因此网络流和最大匹配问题的经典复杂度的上界是难以陈述的。然而，在某些特定参数方案中，上述量子算法优于所有已知的经典算法。（详见文献 [168] 。）

加速：指数描述：给定一个具有$n$个顶点和最大度为$d$的加权图的oracle访问，其边权重表示为电阻。 我们的任务是计算所选顶点对之间的电阻。Wang为这项工作提供了两个量子算法 [210] ，其时间复杂度为$poly(log \ n, d, 1/\phi,1/\epsilon)$，其中$\phi$是图的扩展，且解答被限定在$1+\epsilon$倍真实值之内。已知解决该问题的经典算法的复杂度是$poly(n)$而非$poly(log \ n)$。Wang其中的一个算法是基于量子行走的巧妙应用。另一个则是基于文献 [104] 所提的求解线性方程组量子算法。邻接查询模型中电阻问题的第一个量子查询复杂度的上界由文献 [280] 使用近似张成方案给出。

加速：可变描述：机器学习包含各种各样的计算问题，并且可能受到各种算法技术的攻击。本条目总结了用于改进机器学习的量子算法技术。这里的许多量子算法在其他标题下交叉列出。在文献 [214,222,250,251,309,338,339,359] 中，在数据满足某些特定条件下，求解线性系统的量子算法 [104] 被用于来加速聚类查找（cluster-finding）、主成分分析、二分类（Binary classification）以及各种形式的回归。在文献 [222] 中，这些线性系统的量子算法被应用于加速提取数据集中持久同源（Persistent Homology）的特征。文献 [336] 给出了不基于线性系统算法 [104] 的聚类查找方法。文献 [192,195,344,345,346,347,348] 探索了使用绝热优化技术来加速分类器的训练。文献 [221] 提出了一个训练玻尔兹曼机（Boltzmann machines）的方法，该方法对具有与玻尔兹曼权重成比例的幅度的相干量子态的操纵来实现。通过将Grover搜索和相关技术（例如幅度放大）应用于现有最新经典机器学习算法的子程序，可以获得多项式加速。示例可参见文献 [358,340,341,342,343] 。不属于上述类别之一的其他量子机器学习算法包括 [337,349] 。文献 [246] 很好地总结了量子机器学习算法的一些局限性。提取黑盒函数的隐藏结构的许多其他量子查询算法可以被认为机器学习算法。例子可见文献 [146,23,11,31,212] 。用于学习Majority和Battleship函数的查询算法可见文献 [224] 。文献 [236,237] 给出了从含有噪声的oracle中学习的巨大量子优势。最近的一些综述文章 [299,332,333] 和书籍 [331] 概括了该领域的现状。另外还有大量关于数据本身是量子相干情况下的量子学习相关算法，它们并非严格地限制在量子算法标准设置内。参见文献 [350,334,335,351,352,353,354,355,356,357] 。

加速：多项式描述：如果一个函数$f:\{{0,1\}}^n \rightarrow \{{0,1\}}$取决于其输入比特中的最多$k$个输入比特，那么该函数被称为$k$-小集团的。$k$-小集团测试问题是确定一个给定的函数是$k$-小集团的还是对任意$k$-小集团有$\epsilon$远。尽管并不明显，但其实这个问题与组测试是密切相关的。组测试问题由函数$f:\{{1,2,\dots,n\}}\rightarrow \{{0,1\}}$定义。给定一个访问某函数$F$的Oracle访问，它以$\{{1,2,\dots,n\}}$的子集作为输入。如果存在$x \in S$使得$f(x)=1$，则$F(S)=1$，否则$F(S)=0$。文献 [266] 给出了一个使用$\widetilde{O}(\sqrt{k/\epsilon})$次查询和$\widetilde{O}(n\sqrt{k/\epsilon})$时间的量子算法以解决$k$-小集团测试问题。这是对经典复杂性的二次加速，并且改进了先前在文献 [267] 所提出的$k$-小集测试量子算法。文献 [266] 给出了用于组测试的近似版本的多项式加速，改进了先前文献 [167,268] 中的结果。

加速：超多项式描述：对于任意一个在物理上真实存在的$n$阶自由度哈密顿量$H$, 其对应的时间演化算子$e^{-iHt}$可用$poly(n,t)$个门来实现. 除非BPP=BQP, 否则该问题在经典计算机上无法在多项式时间内求解。对于一般类哈密顿量 [25, 95, 92, 5, 12, 170, 205, 211, 244, 245, 278, 293, 294, 295, 372, 382] , 化学动力学 [63, 68, 227, 310, 375] , 凝聚态物理学 [1, 99, 145] , 相对量子力学(Dirac 和 Klein-Gordon 方程式) [367, 369, 370, 371] , 开放量子系统 [376, 377, 378, 379] , 和量子场论 [107, 166, 228, 229, 230, 368] ，许多量子模拟技术已经取得了进展。 经典模拟量子系统的指数复杂度使得Feynman首次提出量子计算机可能在某些任务上胜过经典计算机 [40] 的想法. 尽管寻找局域哈密顿量的基态能量是QMA-complete 的, 且因此最坏情况下在量子计算机上可能需要指数级时间, 但是已有量子算法近似某些种类的哈密顿的基态 [102, 231, 232, 233, 234, 235, 308, 321, 322, 380, 381] 和热态 [132,121,281,282,307] 。同时也有制备特定类型的张量网络态的高效量子算法 [323, 324, 325, 326, 327, 328] 。

加速：超多项式描述：如Freedman等人在文献 [42,41] 所示, 为$e^{{ i2\pi } /5}$的瓣状闭合Jones多项式寻找一个确定的可加近似是一个BQP-完备问题. Aharonov等人将这个结果推广到对于任意$k$的$e^{{ i2\pi } /k}$ [4,2] . Wocjan和Yard进一步推广了这一结论, 得到了一个估计HOMFLY多项式的量子算法 [93] , 其中Jones多项式是其中一个特例. Aharonov等人随后指出，对于针对平面图的更一般的Tutte多项式，量子计算机可在多项式时间内估计其一个特定的可加近似 [3] 。尚不完全清楚文献 [3] 获得的近似参数在哪个范围是BQP-hard的。(参见配分函数。) 对于有限群量子偶产生的链式不变量，已经发行有可加近似的多项式时间量子算法 [174] 。(该问题不是BQP-hard问题。) 如文献 [83] 所示, 对于$e^{i2\pi /5}$上的一个瓣迹闭合Jones多项式，找出一个特定可加近似的问题是一个DQC1-complete问题。

加速：超多项式描述：Turaev-Viro不变量是利用三维流形作为输入并产生一个实数作为输出的函数. 同胚流形产生相同的数. 给定一个由Heegaard分裂指定的三维流形, 量子计算机可以有效地为其Turaev-Viro不变量找到一个确定的可加近似, 并且该近似是BQP-完备的 [129] . 在 [114] 中，我们给出了一个多项式时间量子算法来可加地近似由外科手术给出的流形的Witten-Reshitikhin-Turaev (WRT)不变量. WRT不变量平方之后得到Turaev-Viro 不变量. 然而, 还不清楚通过 [114] 实现的近似是否是BQP-完全的. 在 [115] 中还提出了量子计算和三流形不变量之间可能存在联系的建议.

加速：超多项式描述：对于一个具有有限状态集$S$的经典系统, 配分函数定义为$Z=\Sigma_{s\in S}e^{-E(s)/kT}$, 其中$T$是温度, $k$是Boltzmann常数。本质上, 每一个热力学量都可以通过取配分函数的一个合适的偏导数来计算。Potts模型的配分函数是Tutte多项式的一个特例。文献 [3] 给出了一个近似Tutte多项式的量子算法。文献 [63] 探讨了这些方法之间的某些联系。文献 [112,113,45,47] 给出了其他一些在量子计算机上估计配分函数的算法。 文献 [113] 也给出一个具有BQP完全性的结果(其中“能量”可以是复数)。文献 [121] 给出了一种通过模拟热化过程来近似配分函数的方法. 文献 [122] 给出了对一般配分方程估计的二次加速。文献 [265] 给出了基于量子游走达到估计配分函数多项式加速的方法。

加速：未知描述：在绝热量子计算中，人们从一个基态易于制备的初始哈密顿量开始，慢慢地将其改变为基态编码一些可计算问题的解另一个哈密顿量。根据绝热定理, 只要哈密顿量的变化足够缓慢, 系统总是保持在其瞬时基态上。一个绝热算法的运行时间最差为$1/\gamma^3$, 其中$\gamma$表示基态与第一激发态之间的最小本征值差值 [185] 。如果一个哈密顿量的变化足够平滑, 可以将其改进到$\widetilde{O}(1/\gamma^2)$ [247] 。绝热量子计算最早由Farhi等人提出，以解决NP完全的组合优化问题 [96,186] 。最优化问题的绝热量子算法通常使用不受符号问题影响的“随机”（”stochastic”）哈密顿量。 这种算法有时被称为量子退火算法。非随机哈密顿量的绝热量子计算与量子电路模型一样强大 [97] 。使用随机哈密顿量的绝热算法或许不那么强大 [183] ，但仍然可能比经典计算更强大。绝热优化算法的渐近运行时间是出了名的难以分析，但已经取得了一些进展 [179,180,181,182,187,188,189,190,191,226] 。（同样相关的还有关于量子退火的早期文献，它最初指的是一种经典的优化算法，通过模拟量子过程来运行，就像模拟退火是一种通过模拟热过程来运行的经典优化算法一样。参见文献 [199,198] 。）绝热量子计算机可以执行一个有点类似于运行时间$O(\sqrt N)$的 Grover搜索 [98] 的过程。通过采用文献 [85] 的技术，文献 [184] 构造了一些绝热量子算法, 对一类更普遍的问题实现二次加速。绝热量子算法已经被提出以解决一些特定的问题, 包括PageRank [176] , 机器学习 [192,195] 和图问题 [193,194] 。一些量子模拟算法也使用到绝热态制备。

加速：超多项式描述：对于许多组合优化问题，找到精确的最优解是NP完全的。另外还有些近似困难(hardness-of-approximation)结果证明找到具有足够小的误差界限的近似解是NP完全的。对于某些问题，多项式时间经典近似算法实现的最佳误差界与证明为NP-hard的误差界之间存在差距。对于这样的问题，量子计算有可能实现指数加速。文献 [242] 提出了一种新的量子算法技术—量子近似优化算法（QAOA），用来寻找组合优化问题的近似解。随后文献 [243] 表明，QAOA解决了一个名为Max E3LIN2的组合优化问题，且具有比当时已知的任何多项式时间经典算法更好的近似比。然而，随后又发现了一种高效经典算法，该算法实现了更好的近似比（实际上，该近似值与近似困难设定的极限相近） [260] 。目前，QAOA相对于经典计算的优势成为一个活跃的研究领域 [300,301,302,314] 。

加速：超多项式描述：给定$m+1$个$n \times n$厄米（Hermitian）矩阵，$C,A_1,A_2,…,A_m$，和m个数，$b_1,b_2,…,b_m$，半定规划问题是找一个$n \times n$的半正定矩阵$X$，使得$Tr( {CX} )$最大化，同时满足约束条件：$Tr( {{A_j}X}) \leqslant {b_j}(j = 1,2,…,m)$。半定规划在运筹学，组合优化和量子信息中有许多应用，且线性规划是半定规划的一种特例。在文献 [313] 的基础上，文献 [383] 给出了一种近似解决半定规划问题的量子算法，在误差为$\pm\varepsilon $时的时间复杂度为$O(\sqrt m log \ m \cdot poly(log \ n,r,{\varepsilon ^{ – 1}}))$，其中，$r$为半定规划的秩。在r相对n较小时，该量子算法相对最快经典算法有二次加速。该量子算法是基于幅度放大和量子吉布斯采样 [121,307] 。

加速：超多项式描述：令f(x,y)是有限域${\mathbb{F}_p}$上的$d$次多项式，$N_r$是拓展域${\mathbb{F}_{{p^r}}}$上$f(x,y)=0$的解的个数。$f$的zeta函数定义为：${Z_f}(T) = exp (\sum_{r = 1}^{r = \infty } {\frac{{{N_r}}}{r}} {T^r})$。注意到，${Z_f}(T)$总是可以写成：${Z_f}(T) = \frac{{{Q_f}(T)}}{{(1 – pT)(1 – T)}}$，其中，${{Q_f}(T)}$是2g阶多项式的，$g =\frac{1}{2}(d – 1)(d – 2)$是f的亏格（genus）。给定 ${Z_f}(T)，可以很容易计算任何拓展域${\mathbb{F}_{p^r}}$上$f$的零点的个数。当定义$f$的原始域没有素数阶，也可以类似的定义zeta函数。文献 [64] 表明量子计算机可以在$poly(log \ p,r,g)$时间内确定有限域${\mathbb{F}_{p^r}}$上亏格$g$曲线的zeta函数。已知的最快经典算法复杂度在$log(p)$或$g$上都是指数的。在一个不同但有些相关的领域，van Dam猜想由于黎曼zeta函数的零点和某些量子算符的特征值之间的联系，量子计算机可能能够有效地近似有限域上方程的解的个数 [87] 。

加速：超多项式描述：设$C$是一个$n$比特码，即$\mathbb{Z}_2^n$的一个子集。$C$的权重计数器为${S_C}(x,y) = \sum_{c \in C} {{x^{| c |}}} {y^{n – | c |}}$，其中$| c |$指$c$的汉明（Hamming）权重。权重计数器在经典编码研究中有许多用途。如果$C$是线性码，则可以通过$C = { c:Ac = 0} $来定义，其中A是$\mathbb{Z}_2$上的矩阵。在这种情况下，${S_C}(x,y) =\sum_{c:Ac = 0} {{x^{| c |}}} {y^{n – | c |}}$。二次带符号权重计数器（Quadratically signed weight enumerators）可以推广为：$S(A,B,x,y) = {\sum_{c:Ac = 0} {( – 1)} ^{{c^T}Bc}}{x^{| c |}}{y^{n – | c |}}$。现在考虑下面这个特例。令A是$\mathbb{Z}_2$上上的一个$n \times n$的矩阵，且$diag(A)=I$。令lwtr(A)为下三角矩阵，这可通过将A对角线上方的所有元素设置为0实现。令I,k为正整数。在保证$| {S(A,lwtr(A),k,l)} | \geqslant \frac{1}{2}{({k^2} + {l^2})^{t\frac{n}{2}}}$的前提下，Knill和Laflamme表明确定$| {S(A,lwtr(A),k,l)} |$的符号的问题是BQP完全的 [65] 。二次带符号权重计数器的估计也与Ising模型和Potts模型的配分函数估计有密切关系 [67,45,46] 。

加速：多项式时间描述：在模拟退火中，由随机矩阵${M_1},{M_2},…{M_n}$定义了一系列马尔科夫链。他们的极限分布${\pi _1},{\pi _2},…,{\pi _n}$满足：$| {{\pi _{t + 1}} – {\pi _t}} | < \varepsilon $，$\varepsilon$是个很小的数。这些分布可以看成是在一系列在连续较低的温度下的热平衡分布。如果${\pi _1}$很容易得到，那么通过这一系列马尔科夫链，可以从${\pi _n}$中采样。典型的情况是，${pi _n}$是某个优化问题的较好的解的一个分布。令${\delta _i}$为M_i的最大特征值与第二大特征值之差，$\delta = {min _i}{\delta _i}$，则经典算法的运行时间正比例于$1/\delta $。基于Szegedy的结果 [135, 85] ，Somma等人指出量子计算机可以以正比于$1/\sqrt{\delta }$的时间从${\pi_n}$中采样 [84,177] 。文献 [265] 给出了用量子行走来加速经典马尔科夫链蒙特卡洛算法的其他算法。

加速：超多项式描述：字符串重写是计算中一个非常基本的模型。字符串重写系统（有时称为语法）由一系列规则确定，这些规则能够运行一些子字符串被其他子字符串代替。例如，上下文无关的语法和下推自动机（pushdown automata）是等价的。Janzing和 Wocjan在文献 [59] 中指出，一个特定的字符串重写问题是PromiseBQP完全的. 因此量子计算机能够在多项式时间解决它，而经典计算机可能不能。给定三个字符串$s,t,t’$，以及一系列满足特定承诺(promises)的字符串重写规则，字符串重写问题是找出一个特定的近似，以近似从$s$获得$t$的路径数与从$t’$获得$t$的路径数之差。类似的，一个图中每对定点之间路径数之差，以及一个随机行走中每对状态转移概率差的特定近似问题也是BQP完全的 [58] 。

加速：超多项式描述：量子计算机在近似指数级大型稀疏矩阵幂的矩阵元素方面具有指数优势。假设我们有一个$N\times N$的对称矩阵$A$，其中每一行中最多有$polylog ( N  )$个非零项；并且给定一个行索引，可以有效地计算出非零项的集合。本算法的任务是，对于任意$1< i< N$和$N$中的任意多重对数$m$，用来近似矩阵$A^m$的第$i^{th}$个对角线矩阵元素$ ( A^m  )_{ii}$。将这个近似值加入$b^m\epsilon$中，其中$b$是给定的$ |A |$的上界，$\epsilon$的阶为$1/polylog ( N )$。如Janzing和Wocjan所示，这个问题和非对角矩阵元素的相应问题一样是PromiseBQP-complete问题 [60] 。因此，量子计算机可以在多项式时间解决它，但经典计算机可能无法在多项式时间解决它。

[1] Daniel S. Abrams and Seth Lloyd. Simulation of many-body Fermi systems on a universal quantum computer. Physical Review Letters, 79(13):2586-2589, 1997. arXiv:quant-ph/9703054

[2] Dorit Aharonov and Itai AradThe BQP-hardness of approximating the Jones polynomial.New Journal of Physics 13:035019, 2011.arXiv:quant-ph/0605181

[3] Dorit Aharonov, Itai Arad, Elad Eban, and Zeph LandauPolynomial quantum algorithms for additive approximations of the Potts model and other points of the Tutte plane.arXiv:quant-ph/0702008, 2007.

[4] Dorit Aharonov, Vaughan Jones, and Zeph LandauA polynomial quantum algorithm for approximating the Jones polynomial.In Proceedings of the 38th ACM Symposium on Theory of Computing, 2006.arXiv:quant-ph/0511096

[5] Dorit Aharonov and Amnon Ta-ShmaAdiabatic quantum state generation and statistical zero knowledge.In Proceedings of the 35th ACM Symposium on Theory of Computing, 2003.arXiv:quant-ph/0301023.

[6] A. Ambainis, H. Buhrman, P. Høyer, M. Karpinizki, and P. KururQuantum matrix verification.Unpublished Manuscript, 2002.

[7] Andris AmbainisQuantum walk algorithm for element distinctness.SIAM Journal on Computing, 37:210-239, 2007.arXiv:quant-ph/0311001

[8] Andris Ambainis, Andrew M. Childs, Ben W.Reichardt, Robert Špalek, and Shengyu ZhengEvery AND-OR formula of size N can be evaluated in timen1/2+o(1)n1/2+o(1)on a quantum computer.In Proceedings of the 48th IEEE Symposium on the Foundations of Computer Science, pages 363-372, 2007.arXiv:quant-ph/0703015 and arXiv:0704.3628

[9] Dave Bacon, Andrew M. Childs, and Wim van DamFrom optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups.In Proceedings of the 46th IEEE Symposium on Foundations of Computer Science, pages 469-478, 2005.arXiv:quant-ph/0504083

[10] Michael Ben-Or and Avinatan HassidimQuantum search in an ordered list via adaptive learning.arXiv:quant-ph/0703231, 2007.

[11] Ethan Bernstein and Umesh VaziraniQuantum complexity theory.In Proceedings of the 25th ACM Symposium on the Theory of Computing, pages 11-20, 1993.

[12] D.W. Berry, G. Ahokas, R. Cleve, and B. C. SandersEfficient quantum algorithms for simulating sparse Hamiltonians.Communications in Mathematical Physics, 270(2):359-371, 2007.arXiv:quant-ph/0508139

[13] A. Berzina, A. Dubrovsky, R. Frivalds, L. Lace, and O. ScegulnajaQuantum query complexity for some graph problems.In Proceedings of the 30th Conference on Current Trends in Theory and Practive of Computer Science, pages 140-150, 2004.

[14] D. Boneh and R. J. LiptonQuantum cryptanalysis of hidden linear functions.In Don Coppersmith, editor, CRYPTO ’95, Lecture Notes in Computer Science, pages 424-437. Springer-Verlag, 1995.

[15] M. Boyer, G. Brassard, P. Høyer, and A. TappTight bounds on quantum searching.Fortschritte der Physik, 46:493-505, 1998.

[16] G. Brassard, P. Høyer, and A. TappQuantum counting.arXiv:quant-ph/9805082, 1998.

[17] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain TappQuantum amplitude amplification and estimation.In Samuel J. Lomonaco Jr. and Howard E. Brandt, editors, Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of AMS Contemporary Mathematics Series. American Mathematical Society, 2002.arXiv:quant-ph/0005055

[18] Gilles Brassard, Peter Høyer, and Alain TappQuantum algorithm for the collision problem.ACM SIGACT News, 28:14-19, 1997.arXiv:quant-ph/9705002

[19] Harry Buhrman and Robert ŠpalekQuantum verification of matrix products.In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms, pages 880-889, 2006.arXiv:quant-ph/0409035

[20] David BulgerQuantum basin hopping with gradient-based local optimisation.arXiv:quant-ph/0507193, 2005.

[21] Harry Burhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, and Ronald de WolfQuantum algorithms for element distinctness.In Proceedings of the 16th IEEE Annual Conference on Computational Complexity, pages 131-137, 2001.arXiv:quant-ph/0007016

[22] Dong Pyo Chi, Jeong San Kim, and Soojoon LeeNotes on the hidden subgroup problem on some semi-direct product groups.Phys. Lett. A 359(2):114-116, 2006.arXiv:quant-ph/0604172

[23] A. M. Childs, L. J. Schulman, and U. V. VaziraniQuantum algorithms for hidden nonlinear structures.In Proceedings of the 48th IEEE Symposium on Foundations of Computer Science, pages 395-404, 2007.arXiv:0705.2784

[24] Andrew Childs and Troy LeeOptimal quantum adversary lower bounds for ordered search.Proceedings of ICALP 2008arXiv:0708.3396

[25] Andrew M. ChildsQuantum information processing in continuous time.PhD thesis, MIT, 2004.

[26] Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. SpielmanExponential algorithmic speedup by quantum walk.In Proceedings of the 35th ACM Symposium on Theory of Computing, pages 59-68, 2003.arXiv:quant-ph/0209131

[27] Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David YeungDiscrete-query quantum algorithm for NAND trees.Theory of Computing, 5:119-123, 2009.arXiv:quant-ph/0702160

[28] Andrew M. Childs and Wim van DamQuantum algorithm for a generalized hidden shift problem.In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms, pages 1225-1232, 2007.arXiv:quant-ph/0507190.

[29] Richard Cleve, Dmitry Gavinsky, and David L. YeungQuantum algorithms for evaluating MIN-MAX trees.In Theory of Quantum Computation, Communication, and Cryptography, pages 11-15,Springer, 2008. (LNCS Vol. 5106)arXiv:0710.5794.

[30] J. Niel de Beaudrap, Richard Cleve, and John WatrousSharp quantum versus classical query complexity separations.Algorithmica, 34(4):449-461, 2002.arXiv:quant-ph/0011065v2.

[31] Thomas Decker, Jan Draisma, and Pawel WocjanQuantum algorithm for identifying hidden polynomials.Quantum Information and Computation, 9(3):215-230, 2009.arXiv:0706.1219.

[32] David DeutschQuantum theory, the Church-Turing principle, and the universal quantum computer.Proceedings of the Royal Society of London Series A, 400:97-117, 1985.

[33] David Deutsch and Richard JozsaRapid solution of problems by quantum computation.Proceedings of the Royal Society of London Series A, 493:553-558, 1992.

[34] Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi MhallaQuantum query complexity of some graph problems.SIAM Journal on Computing, 35(6):1310-1328, 2006.arXiv:quant-ph/0401091.

[35] Christoph Dürr and Peter HøyerA quantum algorithm for finding the minimum.arXiv:quant-ph/9607014, 1996.

[36] Christoph Dürr, Mehdi Mhalla, and Yaohui LeiQuantum query complexity of graph connectivity.arXiv:quant-ph/0303169, 2003.

[37] Mark Ettinger, Peter Høyer, and Emanuel KnillThe quantum query complexity of the hidden subgroup problem is polynomial.Information Processing Letters, 91(1):43-48, 2004.arXiv:quant-ph/0401083.

[38] Edward Farhi, Jeffrey Goldstone, and Sam GutmannA quantum algorithm for the Hamiltonian NAND tree.Theory of Computing 4:169-190, 2008.arXiv:quant-ph/0702144.

[39] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael SipserInvariant quantum algorithms for insertion into an ordered list.arXiv:quant-ph/9901059, 1999.

[40] Richard P. FeynmanSimulating physics with computers.International Journal of Theoretical Physics, 21(6/7):467-488, 1982.

[41] Michael Freedman, Alexei Kitaev, and Zhenghan WangSimulation of topological field theories by quantum computers.Communications in Mathematical Physics, 227:587-603, 2002.

[42] Michael Freedman, Michael Larsen, and Zhenghan WangA modular functor which is universal for quantum computation.Comm. Math. Phys. 227(3):605-622, 2002.arXiv:quant-ph/0001108.

[43] K. Friedl, G. Ivanyos, F. Magniez, M. Santha, and P. SenHidden translation and translating coset in quantum computing.SIAM Journal on Computing Vol. 43, pp. 1-24, 2014.Appeared earlier in Proceedings of the 35th ACM Symposium on Theory of Computing, pages 1-9, 2003.arXiv:quant-ph/0211091.

[44] D. GavinskyQuantum solution to the hidden subgroup problem for poly-near-Hamiltonian-groups.Quantum Information and Computation, 4:229-235, 2004.

[45] Joseph GeraciA new connection between quantum circuits, graphs and the Ising partition functionQuantum Information Processing, 7(5):227-242, 2008.arXiv:0801.4833.

[46] Joseph Geraci and Frank Van BusselA theorem on the quantum evaluation of weight enumerators for a certain class of cyclic Codes with a note on cyclotomic cosets.arXiv:cs/0703129, 2007.

[47] Joseph Geraci and Daniel A. LidarOn the exact evaluation of certain instances of the Potts partition function by quantum computers.Comm. Math. Phys. Vol. 279, pg. 735, 2008.arXiv:quant-ph/0703023.

[48] Lov K. GroverQuantum mechanics helps in searching for a needle in a haystack.Physical Review Letters, 79(2):325-328, 1997.arXiv:quant-ph/9605043.

[49] Sean HallgrenPolynomial-time quantum algorithms for Pell’s equation and the principal ideal problem.In Proceedings of the 34th ACM Symposium on Theory of Computing, 2002.

[50] Sean HallgrenFast quantum algorithms for computing the unit group and class group of a number field.In Proceedings of the 37th ACM Symposium on Theory of Computing, 2005.

[51] Sean Hallgren, Alexander Russell, and Amnon Ta-ShmaNormal subgroup reconstruction and quantum computation using group representations.SIAM Journal on Computing, 32(4):916-934, 2003.

[52] Mark HeiligmanQuantum algorithms for lowest weight paths and spanning trees in complete graphs.arXiv:quant-ph/0303131, 2003.

[53] Yoshifumi Inui and François Le GallEfficient quantum algorithms for the hidden subgroup problem over a class of semi-direct product groups.Quantum Information and Computation, 7(5/6):559-570, 2007.arXiv:quant-ph/0412033.

[54] Yuki Kelly ItakuraQuantum algorithm for commutativity testing of a matrix set.Master’s thesis, University of Waterloo, 2005.arXiv:quant-ph/0509206.

[55] Gábor Ivanyos, Frédéric Magniez, and Miklos SanthaEfficient quantum algorithms for some instances of the non-abelian hidden subgroup problem.In Proceedings of the 13th ACM Symposium on Parallel Algorithms and Architectures, pages 263-270, 2001.arXiv:quant-ph/0102014.

[56] Gábor Ivanyos, Luc Sanselme, and Miklos SanthaAn efficient quantum algorithm for the hidden subgroup problem in extraspecial groups.In Proceedings of the 24th Symposium on Theoretical Aspects of Computer Science, 2007.arXiv:quant-ph/0701235.

[57] Gábor Ivanyos, Luc Sanselme, and Miklos SanthaAn efficient quantum algorithm for the hidden subgroup problem in nil-2 groups.In LATIN 2008: Theoretical Informatics, pg. 759-771, Springer (LNCS 4957).arXiv:0707.1260.

[58] Dominik Janzing and Pawel WocjanBQP-complete problems concerning mixing properties of classical random walks on sparse graphs.arXiv:quant-ph/0610235, 2006.

[59] Dominik Janzing and Pawel WocjanA promiseBQP-complete string rewriting problem.Quantum Information and Computation, 10(3/4):234-257, 2010.arXiv:0705.1180.

[60] Dominik Janzing and Pawel WocjanA simple promiseBQP-complete matrix problem.Theory of Computing, 3:61-79, 2007.arXiv:quant-ph/0606229.

[61] Stephen P. JordanFast quantum algorithm for numerical gradient estimation.Physical Review Letters, 95:050501, 2005.arXiv:quant-ph/0405146.

[62] Stephen P. JordanQuantum Computation Beyond the Circuit Model.PhD thesis, Massachusetts Institute of Technology, 2008.arXiv:0809.2307.

[63] Ivan Kassal, Stephen P. Jordan, Peter J. Love, Masoud Mohseni, and Alán Aspuru-GuzikQuantum algorithms for the simulation of chemical dynamics.Proc. Natl. Acad. Sci. Vol. 105, pg. 18681, 2008.arXiv:0801.2986.

[64] Kiran S. KedlayaQuantum computation of zeta functions of curves.Computational Complexity, 15:1-19, 2006.arXiv:math/0411623.

[65] E. Knill and R. LaflammeQuantum computation and quadratically signed weight enumerators.Information Processing Letters, 79(4):173-179, 2001.arXiv:quant-ph/9909094.

[66] Greg KuperbergA subexponential-time quantum algorithm for the dihedral hidden subgroup problem.SIAM Journal on Computing, 35(1):170-188, 2005.arXiv:quant-ph/0302112.

[67] Daniel A. LidarOn the quantum computational complexity of the Ising spin glass partition function and of knot invariants.New Journal of Physics Vol. 6, pg. 167, 2004.arXiv:quant-ph/0309064.

[68] Daniel A. Lidar and Haobin WangCalculating the thermal rate constant with exponential speedup on a quantum computer.Physical Review E, 59(2):2429-2438, 1999.arXiv:quant-ph/9807009.

[69] Chris LomontThe hidden subgroup problem – review and open problems.arXiv:quant-ph/0411037, 2004.

[70] Frédéric Magniez, Miklos Santha, and Mario SzegedyQuantum algorithms for the triangle problem.SIAM Journal on Computing, 37(2):413-424, 2007.arXiv:quant-ph/0310134.

[71] Carlos Magno, M. Cosme, and Renato PortugalQuantum algorithm for the hidden subgroup problem on a class of semidirect product groups.arXiv:quant-ph/0703223, 2007.

[72] Cristopher Moore, Daniel Rockmore, Alexander Russell, and Leonard SchulmanThe power of basis selection in Fourier sampling: the hidden subgroup problem in affine groups.In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms, pages 1113-1122, 2004.arXiv:quant-ph/0211124.

[73] M. MoscaQuantum searching, counting, and amplitude amplification by eigenvector analysis.In R. Freivalds, editor, Proceedings of International Workshop on Randomized Algorithms, pages 90-100, 1998.

[74] Michele MoscaQuantum Computer Algorithms.PhD thesis, University of Oxford, 1999.

[75] Ashwin Nayak and Felix WuThe quantum query complexity of approximating the median and related statistics.In Proceedings of 31st ACM Symposium on the Theory of Computing, 1999.arXiv:quant-ph/9804066.

[76] Michael A. Nielsen and Isaac L. Chuang.Quantum Computation and Quantum Information.Cambridge University Press, Cambridge, UK, 2000.

[77] Erich NovakQuantum complexity of integration.Journal of Complexity, 17:2-16, 2001.arXiv:quant-ph/0008124.

[78] Oded RegevQuantum computation and lattice problems.In Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002.arXiv:cs/0304005.

[79] Oded RegevA subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space.arXiv:quant-ph/0406151, 2004.

[80] Ben Reichardt and Robert ŠpalekSpan-program-based quantum algorithm for evaluating formulas.Proceedings of STOC 2008arXiv:0710.2630.

[81] Martin Roetteler and Thomas BethPolynomial-time solution to the hidden subgroup problem for a class of non-abelian groups.arXiv:quant-ph/9812070, 1998.

[82] Peter W. ShorPolynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.SIAM Journal on Computing, 26(5):1484-1509, 1997.arXiv:quant-ph/9508027.

[83] Peter W. Shor and Stephen P. JordanEstimating Jones polynomials is a complete problem for one clean qubit.Quantum Information and Computation, 8(8/9):681-714, 2008.arXiv:0707.2831.

[84] R. D. Somma, S. Boixo, and H. BarnumQuantum simulated annealing.arXiv:0712.1008, 2007.

[85] M. SzegedyQuantum speed-up of Markov chain based algorithms.In Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, pg. 32, 2004.

[86] Wim van DamQuantum algorithms for weighing matrices and quadratic residues.Algorithmica, 34(4):413-428, 2002.arXiv:quant-ph/0008059.

[87] Wim van DamQuantum computing and zeros of zeta functions.arXiv:quant-ph/0405081, 2004.

[88] Wim van Dam and Sean HallgrenEfficient quantum algorithms for shifted quadratic character problems.arXiv:quant-ph/0011067, 2000.

[89] Wim van Dam, Sean Hallgren, and Lawrence IpQuantum algorithms for some hidden shift problems.SIAM Journal on Computing, 36(3):763-778, 2006.arXiv:quant-h/0211140.

[90] Wim van Dam and Gadiel SeroussiEfficient quantum algorithms for estimating Gauss sums.arXiv:quant-ph/0207131, 2002.

[91] John WatrousQuantum algorithms for solvable groups.In Proceedings of the 33rd ACM Symposium on Theory of Computing, pages 60-67, 2001.arXiv:quant-ph/0011023.

[92] Stephen WiesnerSimulations of many-body quantum systems by a quantum computer.arXiv:quant-ph/9603028, 1996.

[93] Pawel Wocjan and Jon YardThe Jones polynomial: quantum algorithms and applications in quantum complexity theory.Quantum Information and Computation 8(1/2):147-180, 2008.arXiv:quant-ph/0603069.

[94] Andrew YaoOn computing the minima of quadratic forms.In Proceedings of the 7th ACM Symposium on Theory of Computing, pages 23-26, 1975.

[95] Christof ZalkaEfficient simulation of quantum systems by quantum computers.Proceedings of the Royal Society of London Series A, 454:313, 1996.arXiv:quant-ph/9603026.

[96] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael SipserQuantum computation by adiabatic evolution.arXiv:quant-ph/0001106, 2000.

[97] Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded RegevAdiabatic Quantum Computation is Equivalent to Standard Quantum Computation.SIAM Journal on Computing, 37(1):166-194, 2007.arXiv:quant-ph/0405098

[98] Jérémie Roland and Nicolas J. CerfQuantum search by local adiabatic evolution.Physical Review A, 65(4):042308, 2002.arXiv:quant-ph/0107015

[99] L.-A. Wu, M.S. Byrd, and D. A. LidarPolynomial-Time Simulation of Pairing Models on a Quantum Computer.Physical Review Letters, 89(6):057904, 2002.arXiv:quant-ph/0108110

[100] Eli Biham, Ofer Biham, David Biron, Markus Grassl, and Daniel LidarGrover’s quantum search algorithm for an arbitrary initial amplitude distribution.Physical Review A, 60(4):2742, 1999.arXiv:quant-ph/9807027 and arXiv:quant-ph/0010077

[101] Andrew Childs, Shelby Kimmel, and Robin KothariThe quantum query complexity of read-many formulasIn Proceedings of ESA 2012, pg. 337-348, Springer. (LNCS 7501)arXiv:1112.0548, 2011.

[102] Alán Aspuru-Guzik, Anthony D. Dutoi, Peter J. Love, and Martin Head-GordonSimulated quantum computation of molecular energies.Science, 309(5741):1704-1707, 2005.arXiv:quant-ph/0604193

[103] A. M. Childs, A. J. Landahl, and P. A. ParriloQuantum algorithms for the ordered search problem via semidefinite programming.Physical Review A, 75 032335, 2007.arXiv:quant-ph/0608161

[104] Aram W. Harrow, Avinatan Hassidim, and Seth LloydQuantum algorithm for solving linear systems of equations.Physical Review Letters 15(103):150502, 2009.arXiv:0811.3171.

[105] Martin RoettelerQuantum algorithms for highly non-linear Boolean functions.Proceedings of SODA 2010arXiv:0811.3208.

[106] Stephen P. JordanFast quantum algorithms for approximating the irreducible representations of groups.arXiv:0811.0562, 2008.

[107] Tim Byrnes and Yoshihisa YamamotoSimulating lattice gauge theories on a quantum computer.Physical Review A, 73, 022328, 2006.arXiv:quant-ph/0510027.

[108] D. SimonOn the Power of Quantum Computation.In Proceedings of the 35th Symposium on Foundations of Computer Science, pg. 116-123, 1994.

[109] John Proos and Christof ZalkaShor’s discrete logarithm quantum algorithm for elliptic curves.Quantum Information and Computation, Vol. 3, No. 4, pg.317-344, 2003.arXiv:quant-ph/0301141.

[110] Yi-Kai LiuQuantum algorithms using the curvelet transform.Proceedings of STOC 2009, pg. 391-400.arXiv:0810.4968.

[111] Wim van Dam and Igor ShparlinskiClassical and quantum algorithms for exponential congruences.Proceedings of TQC 2008, pg. 1-10.arXiv:0804.1109.

[112] Itai Arad and Zeph LandauQuantum computation and the evaluation of tensor networks.SIAM Journal on Computing, 39(7):3089-3121, 2010.arXiv:0805.0040.

[113] M. Van den Nest, W. Dür, R. Raussendorf, and H. J. BriegelQuantum algorithms for spin models and simulable gate sets for quantum computation.Physical Review A, 80:052334, 2009.arXiv:0805.1214.

[114] Silvano Garnerone, Annalisa Marzuoli, and Mario RasettiEfficient quantum processing of 3-manifold topological invariants.Advances in Theoretical and Mathematical Physics, 13(6):1601-1652, 2009.arXiv:quant-ph/0703037.

[115] Louis H. Kauffman and Samuel J. Lomonaco Jr.q-deformed spin networks, knot polynomials and anyonic topological quantum computation.Journal of Knot Theory, Vol. 16, No. 3, pg. 267-332, 2007.arXiv:quant-ph/0606114.

[116] Arthur Schmidt and Ulrich VollmerPolynomial time quantum algorithm for the computation of the unit group of a number field.In Proceedings of the 37th Symposium on the Theory of Computing, pg. 475-480, 2005.

[117] Sergey Bravyi, Aram Harrow, and Avinatan HassidimQuantum algorithms for testing properties of distributions.IEEE Transactions on Information Theory 57(6):3971-3981, 2011.arXiv:0907.3920.

[118] Pawel M. Wocjan, Stephen P. Jordan, Hamed Ahmadi, and Joseph P. BrennanEfficient quantum processing of ideals in finite rings.arXiv:0908.0022, 2009.

[119] V. Arvind, Bireswar Das, and Partha MukhopadhyayThe complexity of black-box ring problems.In Proceedings of COCCOON 2006, pg 126-145.

[120] V. Arvind and Partha MukhopadhyayQuantum query complexity of multilinear identity testing.In Proceedings of STACS 2009, pg. 87-98.

[121] David Poulin and Pawel WocjanSampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer.Physical Review Letters 103:220502, 2009.arXiv:0905.2199

[122] Pawel Wocjan, Chen-Fu Chiang, Anura Abeyesinghe, and Daniel NagajQuantum speed-up for approximating partition functions.Physical Review A 80:022340, 2009.arXiv:0811.0596

[123] Ashley MontanaroQuantum search with advice.In Proceedings of the 5th conference on Theory of quantum computation, communication, and cryptography (TQC 2010)arXiv:0908.3066

[124] Laszlo Babai, Robert Beals, and Akos SeressPolynomial-time theory of matrix groups.In Proceedings of STOC 2009, pg. 55-64.

[125] Peter ShorAlgorithms for Quantum Computation: Discrete Logarithms and Factoring.In Proceedings of FOCS 1994, pg. 124-134.

[126] Aaron Denney, Cristopher Moore, and Alex RussellFinding conjugate stabilizer subgroups in PSL(2;q) and related groups.Quantum Information and Computation 10(3):282-291, 2010.arXiv:0809.2445.

[127] Kevin K. H. Cheung and Michele MoscaDecomposing finite Abelian groups.Quantum Information and Computation 1(2):26-32, 2001.arXiv:cs/0101004.

[128] François Le GallAn efficient quantum algorithm for some instances of the group isomorphism problem.In Proceedings of STACS 2010.arXiv:1001.0608.

[129] Gorjan Alagic, Stephen Jordan, Robert Koenig, and Ben ReichardtApproximating Turaev-Viro 3-manifold invariants is universal for quantum computation.Physical Review A 82, 040302(R), 2010.arXiv:1003.0923

[130] Martin RöttelerQuantum algorithms to solve the hidden shift problem for quadratics and for functions of large Gowers norm.In Proceedings of MFCS 2009, pg 663-674.arXiv:0911.4724.

[131] Arthur SchmidtQuantum Algorithms for many-to-one Functions to Solve the Regulator and the Principal Ideal Problem.arXiv:0912.4807, 2009.

[132] K. Temme, T.J. Osborne, K.G. Vollbrecht, D. Poulin, and F. VerstraeteQuantum Metropolis Sampling.Nature, Vol. 471, pg. 87-90, 2011.arXiv:0911.3635.

[133] Andris AmbainisQuantum Search Algorithms.SIGACT News, 35 (2):22-35, 2004.arXiv:quant-ph/0504012

[134] Nicolas J. Cerf, Lov K. Grover, and Colin P. WilliamsNested quantum search and NP-hard problems.Applicable Algebra in Engineering, Communication and Computing, 10 (4-5):311-338, 2000.

[135] Mario SzegedySpectra of Quantized Walks and aδϵ−−√δϵrule.arXiv:quant-ph/0401053, 2004.

[136] Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, and Junichi TeruyamaQuantum Counterfeit Coin Problems.In Proceedings of 21st International Symposium on Algorithms and Computation (ISAAC2010), LNCS 6506, pp.73-84, 2010.arXiv:1009.0416

[137] Barbara Terhal and John SmolinSingle quantum querying of a database.Physical Review A 58:1822, 1998.arXiv:quant-ph/9705041

[138] Andris AmbainisVariable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations.arXiv:1010.4458, 2010.

[139] Frédéric Magniez and Ashwin NayakQuantum complexity of testing group commutativity.In Proceedings of 32nd International Colloquium on Automata, Languages and Programming. LNCS 3580, pg. 1312-1324, 2005.arXiv:quant-ph/0506265

[140] Andrew Childs and Robin KothariQuantum query complexity of minor-closed graph properties.In Proceedings of the 28th Symposium on Theoretical Aspects of Computer Science (STACS 2011), pg. 661-672arXiv:1011.1443

[141] Frédéric Magniez, Ashwin Nayak, Jérémie Roland, and Miklos SanthaSearch via quantum walk.In Proceedings STOC 2007, pg. 575-584.arXiv:quant-ph/0608026

[142] Dmitry Gavinsky, Martin Roetteler, and Jérémy RolandQuantum algorithm for the Boolean hidden shift problem.In Proceedings of the 17th annual international conference on Computing and combinatorics (COCOON ’11), 2011.arXiv:1103.3017

[143] Mark Ettinger and Peter HøyerOn quantum algorithms for noncommutative hidden subgroups.Advances in Applied Mathematics, Vol. 25, No. 3, pg. 239-251, 2000.arXiv:quant-ph/9807029

[144] Andris Ambainis, Andrew Childs, and Yi-Kai LiuQuantum property testing for bounded-degree graphs.In Proceedings of RANDOM ’11: Lecture Notes in Computer Science 6845, pp. 365-376, 2011.arXiv:1012.3174

[145] G. Ortiz, J.E. Gubernatis, E. Knill, and R. LaflammeQuantum algorithms for Fermionic simulations.Physical Review A 64: 022319, 2001.arXiv:cond-mat/0012334

[146] Ashley MontanaroThe quantum query complexity of learning multilinear polynomials.Information Processing Letters, 112(11):438-442, 2012.arXiv:1105.3310.

[147] Tad HoggHighly structured searches with quantum computers.Physical Review Letters 80: 2473, 1998.

[148] Markus Hunziker and David A. MeyerQuantum algorithms for highly structured search problems.Quantum Information Processing, Vol. 1, No. 3, pg. 321-341, 2002.

[149] Ben ReichardtSpan programs and quantum query complexity: The general adversary bound is nearly tight for every Boolean function.In Proceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS ’09), pg. 544-551, 2009.arXiv:0904.2759

[150] Aleksandrs BelovsSpan-program-based quantum algorithm for the rank problem.arXiv:1103.0842, 2011.

[151] Sebastian Dörn and Thomas ThieraufThe quantum query complexity of the determinant.Information Processing Letters Vol. 109, No. 6, pg. 305-328, 2009.

[152] Aleksandrs BelovsSpan programs for functions with constant-sized 1-certificates.In Proceedings of STOC 2012, pg. 77-84.arXiv:1105.4024.

[153] Troy Lee, Frédéric Magniez, and Mikos SanthaA learning graph based quantum query algorithm for finding constant-size subgraphs.Chicago Journal of Theoretical Computer Science, Vol. 2012, Article 10, 2012.arXiv:1109.5135.

[154] Aleksandrs Belovs and Troy LeeQuantum algorithm for k-distinctness with prior knowledge on the input.arXiv:1108.3022, 2011.

[155] François Le GallImproved output-sensitive quantum algorithms for Boolean matrix multiplication.In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’12), 2012.

[156] Dominic BerryQuantum algorithms for solving linear differential equations.arXiv:1010.2745, 2010.

[157] Virginia Vassilevska Williams and Ryan WilliamsSubcubic equivalences between path, matrix, and triangle problems.In 51st IEEE Symposium on Foundations of Computer Science (FOCS ’10) pg. 645 – 654, 2010.

[158] Ben W. ReichardtReflections for quantum query algorithms.In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA), pg. 560-569, 2011.arXiv:1005.1601

[159] Ben W. ReichardtSpan-program-based quantum algorithm for evaluating unbalanced formulas.arXiv:0907.1622, 2009.

[160] Ben W. ReichardtFaster quantum algorithm for evaluating game trees.In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA), pg. 546-559, 2011.arXiv:0907.1623

[161] Stacey Jeffery, Robin Kothari, and Frédéric MagniezImproving quantum query complexity of Boolean matrix multiplication using graph collision.In Proceedings of ICALP 2012, pg. 522-532.arXiv:1112.5855.

[162] Andrew M. Childs and Jason M. EisenbergQuantum algorithms for subset finding.Quantum Information and Computation 5(7):593-604, 2005.arXiv:quant-ph/0311038.

[163] Aleksandrs Belovs and Robert ŠpalekAdversary lower bound for the k-sum problem.In Proceedings of ITCS 2013, pg. 323-328.arXiv:1206.6528.

[164] Bohua Zhan, Shelby Kimmel, and Avinatan HassidimSuper-polynomial quantum speed-ups for Boolean evaluation trees with hidden structure.ITCS 2012: Proceedings of the 3rd Innovations in Theoretical Computer Science, ACM, pg. 249-265.arXiv:1101.0796

[165] Shelby KimmelQuantum adversary (upper) bound.39th International Colloquium on Automata, Languages and Programming – ICALP 2012 Volume 7391, p. 557-568.arXiv:1101.0797

[166] Stephen Jordan, Keith Lee, and John PreskillQuantum algorithms for quantum field theories.Science, Vol. 336, pg. 1130-1133, 2012.arXiv:1111.3633

[167] Andris Ambainis and Ashley MontanaroQuantum algorithms for search with wildcards and combinatorial group testing.arXiv:1210.1148, 2012.

[168] Andris Ambainis and Robert ŠpalekQuantum algorithms for matching and network flows.Proceedings of STACS 2007, pg. 172-183.arXiv:quant-ph/0508205

[169] Nathan Wiebe, Daniel Braun, and Seth LloydQuantum data-fitting.Physical Review Letters 109, 050505, 2012.arXiv:1204.5242

[170] Andrew Childs and Nathan WiebeHamiltonian simulation using linear combinations of unitary operations.Quantum Information and Computation 12, 901-924, 2012.arXiv:1202.5822

[171] Stacey Jeffery, Robin Kothari, and Frédéric MagniezNested quantum walks with quantum data structures.In Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA’13), pg. 1474-1485, 2013.arXiv:1210.1199

[172] Aleksandrs BelovsLearning-graph-based quantum algorithm for k-distinctness.Proceedings of STOC 2012, pg. 77-84.arXiv:1205.1534, 2012.

[173] Andrew Childs, Stacey Jeffery, Robin Kothari, and Frédéric MagniezA time-efficient quantum walk for 3-distinctness using nested updates.arXiv:1302.7316, 2013.

[174] Hari Krovi and Alexander RussellQuantum Fourier transforms and the complexity of link invariants for quantum doubles of finite groups.Commun. Math. Phys. 334, 743-777, 2015arXiv:1210.1550

[175] Troy Lee, Frédéric Magniez, and Miklos SanthaImproved quantum query algorithms for triangle finding and associativity testing.arXiv:1210.1014, 2012.

[176] Silvano Garnerone, Paolo Zanardi, and Daniel A. LidarAdiabatic quantum algorithm for search engine ranking.Physical Review Letters 108:230506, 2012.

[177] R. D. Somma, S. Boixo, H. Barnum, and E. KnillQuantum simulations of classical annealing.Physical Review Letters 101:130504, 2008.arXiv:0804.1571

[178] Daniel J. Bernstein, Stacey Jeffery, Tanja Lange, and Alexander MeurerQuantum algorithms for the subset-sum problem.from cr.yp.to.

[179] Boris Altshuler, Hari Krovi, and Jérémie RolandAnderson localization casts clouds over adiabatic quantum optimization.Proceedings of the National Academy of Sciences 107(28):12446-12450, 2010.arXiv:0912.0746

[180] Ben ReichardtThe quantum adiabatic optimization algorithm and local minima.In Proceedings of STOC 2004, pg. 502-510. [Erratum].

[181] Edward Farhi, Jeffrey Goldstone, and Sam GutmannQuantum adiabatic evolution algorithms versus simulated annealing.arXiv:quant-ph/0201031, 2002.

[182] E. Farhi, J. Goldstone, D. Gosset, S. Gutmann, H. B. Meyer, and P. ShorQuantum adiabatic algorithms, small gaps, and different paths.Quantum Information and Computation, 11(3/4):181-214, 2011.arXiv:0909.4766.

[183] Sergey Bravyi, David P. DiVincenzo, Roberto I. Oliveira, and Barbara M. TerhalThe Complexity of Stoquastic Local Hamiltonian Problems.Quantum Information and Computation, 8(5):361-385, 2008.arXiv:quant-ph/0606140.

[184] Rolando D. Somma and Sergio BoixoSpectral gap amplification.SIAM Journal on Computing, 42:593-610, 2013.arXiv:1110.2494.

[185] Sabine Jansen, Mary-Beth Ruskai, Ruedi SeilerBounds for the adiabatic approximation with applications to quantum computation.Journal of Mathematical Physics, 48:102111, 2007.arXiv:quant-ph/0603175.

[186] E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. PredaA Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem.Science, 292(5516):472-475, 2001.arXiv:quant-ph/0104129.

[187] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Daniel NagajHow to make the quantum adiabatic algorithm fail.International Journal of Quantum Information, 6(3):503-516, 2008.arXiv:quant-ph/0512159.

[188] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Daniel NagajUnstructured randomness, small gaps, and localization.Quantum Information and Computation, 11(9/10):840-854, 2011.arXiv:1010.0009.

[189] Edward Farhi, Jeffrey Goldstone, Sam GutmannQuantum adiabatic evolution algorithms with different paths.arXiv:quant-ph/0208135, 2002.

[190] Wim van Dam, Michele Mosca, and Umesh VaziraniHow powerful is adiabatic quantum computation?In Proceedings of FOCS 2001, pg. 279-287.arXiv:quant-ph/0206003 [See also this.]

[191] E. Farhi, D. Gosset, I. Hen, A. W. Sandvik, P. Shor, A. P. Young, and F. ZamponiThe performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs.Physical Review A, 86:052334, 2012.arXiv:1208.3757.

[192] Kristen L. Pudenz and Daniel A. LidarQuantum adiabatic machine learning.Quantum Information Processing, 12:2027, 2013.arXiv:1109.0325.

[193] Frank Gaitan and Lane ClarkRamsey numbers and adiabatic quantum computing.Physical Review Letters, 108:010501, 2012.arXiv:1103.1345.

[194] Frank Gaitan and Lane ClarkGraph isomorphism and adiabatic quantum computing.Physical Review A, 89(2):022342, 2014.arXiv:1304.5773, 2013.

[195] Hartmut Neven, Vasil S. Denchev, Geordie Rose, and William G. MacreadyTraining a binary classifier with the quantum adiabatic algorithm.arXiv:0811.0416, 2008.

[196] Robert BealsQuantum computation of Fourier transforms over symmetric groups.In Proceedings of STOC 1997, pg. 48-53.

[197] Dave Bacon, Isaac L. Chuang, and Aram W. HarrowThe quantum Schur transform: I. efficient qudit circuits.In Proceedings of SODA 2007, pg. 1235-1244.arXiv:quant-ph/0601001.

[198] S. Morita, H. NishimoriMathematical foundation of quantum annealing.Journal of Methematical Physics, 49(12):125210, 2008.

[199] A. B. Finnila, M. A. Gomez, C. Sebenik, C. Stenson, J. D. DollQuantum annealing: a new method for minimizing multidimensional functions.Chemical Physics Letters, 219:343-348, 1994.

[200] D. Gavinsky and T. ItoA quantum query algorithm for the graph collision problem.arXiv:1204.1527, 2012.

[201] Andris Ambainis, Kaspars Balodis, Jānis Iraids, Raitis Ozols, and Juris SmotrovsParameterized quantum query complexity of graph collision.arXiv:1305.1021, 2013.

[202] Kevin C. ZatloukalClassical and quantum algorithms for testing equivalence of group extensions.arXiv:1305.1327, 2013.

[203] Andrew Childs and Gábor IvanyosQuantum computation of discrete logarithms in semigroups.arXiv:1310.6238, 2013.

[204] Matan Banin and Boaz TsabanA reduction of semigroup DLP to classic DLP.arXiv:1310.7903, 2013.

[205] D. W. Berry, R. Cleve, and R. D. SommaExponential improvement in precision for Hamiltonian-evolution simulation.arXiv:1308.5424, 2013.

[206] François Le Gall and Harumichi NishimuraQuantum algorithms for matrix products over semirings.arXiv:1310.3898, 2013.

[207] Nolan WallachA quantum polylog algorithm for non-normal maximal cyclic hidden subgroups in the affine group of a finite field.arXiv:1308.1415, 2013.

[208] Lov GroverFixed-point quantum search.Phys. Rev. Lett. 95(15):150501, 2005.arXiv:quant-ph/0503205

[209] Tathagat Tulsi, Lov Grover, and Apoorva PatelA new algorithm for fixed point quantum search.Quantum Information and Computation 6(6):483-494, 2005.arXiv:quant-ph/0505007

[210] Guoming WangQuantum algorithms for approximating the effective resistances of electrical networks.arXiv:1311.1851

[211] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. SommaExponential improvement in precision for simulating sparse HamiltoniansarXiv:1312.1414

[212] Thomas Decker, Peter Høyer, Gabor Ivanyos, and Miklos SanthaPolynomial time quantum algorithms for certain bivariate hidden polynomial problemsarXiv:1305.1543

[213] Kirsten Eisenträger, Sean Hallgren, Alexei Kitaev, and Fang SongA quantum algorithm for computing the unit group of an arbitrary degree number fieldIn Proceedings of STOC 2014 pg. 293-302.

[214] Seth Lloyd, Masoud Mohseni, and Patrick RobentrostQuantum algorithms for supervised and unsupervised machine learningarXiv:1307.0411

[215] Ashley MontanaroQuantum pattern matching fast on averagearXiv:1408.1816

[216] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh VaziraniStrengths and weaknesses of quantum computingSIAM J. Comput. 26(5):1524-1540, 1997arXiv:quant-ph/9701001

[217] H. Ramesh and V. VinayString matching inO˜(n−−√+m−−√)O~(n+m)quantum timeJournal of Discrete Algorithms 1:103-110, 2003arXiv:quant-ph/0011049

[218] Greg KuperbergAnother subexponential-time quantum algorithm for the dihedral hidden subgroup problemIn Proceedings of TQC pg. 20-34, 2013arXiv:1112.3333

[219] Peter Høyer, Jan Neerbek, and Yaoyun ShiQuantum complexities of ordered searching, sorting, and element distinctnessIn Proceedings of ICALP pg. 346-357, 2001arXiv:quant-ph/0102078

[220] Amnon Ta-ShmaInverting well conditioned matrices in quantum logspaceIn Proceedings of STOC 2013 pg. 881-890.

[221] Nathan Wiebe, Ashish Kapoor, and Krysta SvoreQuantum deep learningarXiv:1412.3489

[222] Seth Lloyd, Silvano Garnerone, and Paolo ZanardiQuantum algorithms for topological and geometric analysis of big dataarXiv:1408.3106

[223] David A. Meyer and James PommersheimSingle-query learning from abelian and non-abelian Hamming distance oraclesarXiv:0912.0583

[224] Markus Hunziker, David A. Meyer, Jihun Park, James Pommersheim, and Mitch RothsteinThe geometry of quantum learningQuantum Information Processing 9:321-341, 2010.arXiv:quant-ph/0309059

[225] Lawrence M. Ioannou and Michele MoscaLimitations on some simple adiabatic quantum algorithmsInternational Journal of Quantum Information, 6(3):419-426, 2008.arXiv:quant-ph/0702241

[226] Michael Jarret and Stephen P. JordanAdiabatic optimization without local minimaQuantum Information and Computation, 15(3/4):0181-0199, 2015.arXiv:1405.7552

[227] Matthew B. Hastings, Dave Wecker, Bela Bauer, and Matthias TroyerImproving quantum algorithms for quantum chemistryQuantum Information and Computation, 15(1/2):0001-0021, 2015.arXiv:1403.1539

[228] Stephen P. Jordan, Keith S. M. Lee, and John PreskillQuantum simulation of scattering in scalar quantum field theoriesQuantum Information and Computation, 14(11/12):1014-1080, 2014.arXiv:1112.4833

[229] Stephen P. Jordan, Keith S. M. Lee, and John PreskillQuantum algorithms for fermionic quantum field theoriesarXiv:1404.7115

[230] Gavin K. Brennen, Peter Rohde, Barry C. Sanders, and Sukhi SinghMulti-scale quantum simulation of quantum field theory using waveletsarXiv:1412.0750

[231] Hefeng Wang, Sabre Kais, Alán Aspuru-Guzik, and Mark R. Hoffmann.Quantum algorithm for obtaining the energy spectrum of molecular systemsPhysical Chemistry Chemical Physics, 10(35):5388-5393, 2008.arXiv:0907.0854

[232] Ivan Kassal and Alán Aspuru-GuzikQuantum algorithm for molecular properties and geometry optimizationJournal of Chemical Physics, 131(22), 2009.arXiv:0908.1921

[233] James D. Whitfield, Jacob Biamonte, and Alán Aspuru-GuzikSimulation of electronic structure Hamiltonians using quantum computersMolecular Physics, 109(5):735-750, 2011.arXiv:1001.3855

[234] Borzu Toloui and Peter J. LoveQuantum algorithms for quantum chemistry based on the sparsity of the CI-matrixarXiv:1312.2529

[235] James D. WhitfieldSpin-free quantum computational simulations and symmetry adapted statesJournal of Chemical Physics, 139(2):021105, 2013.arXiv:1306.1147

[236] Andrew W. Cross, Graeme Smith, and John A. SmolinQuantum learning robust to noisearXiv:1407.5088

[237] Aram W. Harrow and David J. RosenbaumUselessness for an oracle model with internal randomnessQuantum Information and Computation 14(7/8):608-624, 2014arXiv:1111.1462

[238] Jon R. Grice and David A. MeyerA quantum algorithm for Viterbi decoding of classical convolutional codesarXiv:1405.7479

[239] Alexander Barg and Shiyu ZhouA quantum decoding algorithm of the simplex codeProceedings of the 36th Annual Allerton Conference, 1998Available at author’s homepage.

[240] Guoming WangSpan-program-based quantum algorithm for tree detectionarXiv:1309.7713, 2013.

[241] François Le Gall, Harumichi Nishimura, and Seiichiro TaniQuantum algorithm for finding constant-sized sub-hypergraphs over 3-uniform hypergraphsIn Proceedings of COCOON, 2014. pg. 429-440arXiv:1310.4127

[242] Edward Farhi, Jeffrey Goldstone, and Sam GutmannA quantum approximate optimization algorithmarXiv:1411.4028, 2014.

[243] Edward Farhi, Jeffrey Goldstone, and Sam GutmannA quantum approximate optimization algorithm applied to a bounded occurrence constraint problemarXiv:1412.6062, 2014.

[244] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. SommaSimulating Hamiltonian dynamics with a truncated Taylor seriesarXiv:1412.4687, 2014.

[245] Dominic W. Berry, Andrew M. Childs, and Robin KothariHamiltonian simulation with nearly optimal dependence on all parametersarXiv:1501.01715, 2015.

[246] Scott AaronsonRead the fine printNature Physics 11:291-293, 2015.[fulltext]

[247] Alexander Elgart and George A. HagedornA note on the switching adiabatic theoremJournal of Mathematical Physics 53(10):102202, 2012.arXiv:1204.2318

[248] Daniel J. Bernstein, Johannes Buchmann, and Erik Dahmen, Eds.Post-Quantum CryptographySpringer, 2009.

[249] B. D. Clader, B. C. Jacobs, and C. R. SprousePreconditioned quantum linear system algorithmPhys. Rev. Lett. 110:250504, 2013.arXiv:1301.2340

[250] S. Lloyd, M. Mohseni, and P. RebentrostQuantum principal component analysisNature Physics. 10(9):631, 2014.arXiv:1307.0401

[251] Patrick Rebentrost, Masoud Mohseni, and Seth LloydQuantum support vector machine for big data classificationPhys. Rev. Lett. 113, 130503, 2014.arXiv:1307.0471

[252] J. M. PollardTheorems on factorization and primality testingProceedings of the Cambridge Philosophical Society. 76:521-228, 1974.

[253] L. Babai, R. Beals, and A. SeressPolynomial-time theory of matrix groupsIn Proceedings of STOC 2009, pg. 55-64.

[254] Neil J. Ross and Peter SelingerOptimal ancilla-free Clifford+T approximations of z-rotationsarXiv:1403.2975, 2014.

[255] L. A. B. Kowada, C. Lavor, R. Portugal, and C. M. H. de FigueiredoA new quantum algorithm for solving the minimum searching problemInternational Journal of Quantum Information, Vol. 6, No. 3, pg. 427-436, 2008.

[256] Sean Hallgren and Aram HarrowSuperpolynomial speedups based on almost any quantum circuitProceedings of ICALP 2008, pg. 782-795.arXiv:0805.0007

[257] Fernando G.S.L. Brandao and Michal HorodeckiExponential quantum speed-ups are genericQuantum Information and Computation, Vol. 13, Pg. 0901, 2013arXiv:1010.3654

[258] Scott Aaronson and Andris AmbainisForrelation: A problem that optimally separates quantum from classical computing.arXiv:1411.5729, 2014.

[259] Z. GedikComputational speedup with a single qutritarXiv:1403.5861, 2014.

[260] Boaz Barak, Ankur Moitra, Ryan O’Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, and John WrightBeating the random assignment on constraint satisfaction problems of bounded degreearXiv:1505.03424, 2015.

[261] David CornwellAmplified Quantum TransformsarXiv:1406.0190, 2015.

[262] T. Laarhoven, M. Mosca, and J. van de PolSolving the shortest vector problem in lattices faster using quantum searchProceedings of PQCrypto13, pp. 83-101, 2013.arXiv:1301.6176

[263] Andrew M. Childs, Robin Kothari, and Rolando D. SommaQuantum linear systems algorithm with exponentially improved dependence on precisionarXiv:1511.02306, 2015.

[264] Ashley MontanaroQuantum walk speedup of backtracking algorithmsarXiv:1509.02374, 2015.

[265] Ashley MontanaroQuantum speedup of Monte Carlo methodsarXiv:1504.06987, 2015.

[266] Andris Ambainis, Aleksandrs Belovs, Oded Regev, and Ronald de WolfEfficient quantum algorithms for (gapped) group testing and junta testingarXiv:1507.03126, 2015.

[267] A. Atici and R. A. ServedioQuantum algorithms for learning and testing juntasQuantum Information Processing, 6(5):323-348, 2007.arXiv:0707.3479

[268] Aleksandrs BelovsQuantum algorithms for learning symmetric juntas via the adversary boundComputational Complexity, 24(2):255-293, 2015.(Also appears in proceedings of CCC’14).arXiv:1311.6777

[269] Stacey Jeffery and Shelby KimmelNAND-trees, average choice complexity, and effective resistancearXiv:1511.02235, 2015.

[270] Scott Aaronson, Shalev Ben-David, and Robin Kothari. Separations in query complexity using cheat sheets. arXiv:1511.01937, 2015.

[271] Frédéric Grosshans, Thomas Lawson, François Morain, and Benjamin Smith. Factoring safe semiprimes with a single quantum query. arXiv:1511.04385, 2015.

[272] Agnis Āriņš. Span-program-based quantum algorithms for graph bipartiteness and connectivity. arXiv:1510.07825, 2015.

[273] Juan Bermejo-Vega and Kevin C. Zatloukal. Abelian hypergroups and quantum computation. arXiv:1509.05806, 2015.

[274] Andrew Childs and Jeffrey Goldstone. Spatial search by quantum walk. Physical Review A, 70:022314, 2004.arXiv:quant-ph/0306054

[275] Shantanav Chakraborty, Leonardo Novo, Andris Ambainis, and Yasser Omar. Spatial search by quantum walk is optimal for almost all graphs. arXiv:1508.01327, 2015.

[276] François Le Gall. Improved quantum algorithm for triangle finding via combinatorial arguments. In Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pg. 216-225, 2014. arXiv:1407.0085

[277] Ashley Montanaro. The quantum complexity of approximating the frequency moments. arXiv:1505.00113, 2015.

[278] Rolando D. Somma. Quantum simulations of one dimensional quantum systems. arXiv:1503.06319, 2015.

[279] Bill Fefferman and Cedric Yen-Yu Lin. A complete characterization of unitary quantum space. arXiv:1604.01384, 2016.

[280] Tsuyoshi Ito and Stacey Jeffery. Approximate span programs. arXiv:1507.00432, 2015.

[281] Arnau Riera, Christian Gogolin, and Jens Eisert. Thermalization in nature and on a quantum computer. Physical Review Letters, 108:080402 (2012)arXiv:1102.2389.

[282] Michael J. Kastoryano and Fernando G. S. L. Brandao. Quantum Gibbs Samplers: the commuting case. Communications in Mathematical Physics, 344(3):915-957 (2016)arXiv:1409.3435.

[283] Andrew M. Childs, David Jao, and Vladimir Soukharev. Constructing elliptic curve isogenies in quantum subexponential time. Journal of Mathematical Cryptology, 8(1):1-29 (2014)arXiv:1012.4019.

[284] Markus Grassl, Brandon Langenberg, Martin Roetteler, and Rainer Steinwandt. Applying Grover’s algorithm to AES: quantum resource estimates. arXiv:1512.04965, 2015.

[285] M. Ami, O. Di Matteo, V. Gheorghiu, M. Mosca, A. Parent, and J. Schanck. Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3. arXiv:1603.09383, 2016.

[286] Marc Kaplan, Gaetan Leurent, Anthony Leverrier, and Maria Naya-Plasencia. Quantum differential and linear cryptanalysis. arXiv:1510.05836, 2015.

[287] Scott Fluhrer. Quantum Cryptanalysis of NTRU. Cryptology ePrint Archive: Report 2015/676, 2015.

[288] Marc Kaplan. Quantum attacks against iterated block ciphers. arXiv:1410.1434, 2014.

[289] H. Kuwakado and M. Morii. Quantum distinguisher between the 3-round Feistel cipher and the random permutation. In Proceedings of IEEE International Symposium on Information Theory (ISIT), pg. 2682-2685, 2010.

[290] H. Kuwakado and M. Morii. Security on the quantum-type Even-Mansour cipher. In Proceedings of International Symposium on Information Theory and its Applications (ISITA), pg. 312-316, 2012.

[291] Martin Roetteler and Rainer Steinwandt. A note on quantum related-key attacks. arXiv:1306.2301, 2013.

[292] Thomas Santoli and Christian Schaffner. Using Simon’s algorithm to attack symmetric-key cryptographic primitives. arXiv:1603.07856, 2016.

[293] Rolando D. Somma. A Trotter-Suzuki approximation for Lie groups with applications to Hamiltonian simulation. arXiv:1512.03416, 2015.

[294] Guang Hao Low and Isaac Chuang. Optimal Hamiltonian simulation by quantum signal processing. arXiv:1606.02685, 2016.

[295] Dominic W. Berry and Leonardo Novo. Corrected quantum walk for optimal Hamiltonian simulation. arXiv:1606.03443, 2016.

[296] Ashley Montanaro and Sam Pallister. Quantum algorithms and the finite element method. arXiv:1512.05903, 2015.

[297] Lin-Chun Wan, Chao-Hua Yu, Shi-Jie Pan, Fei Gao, and Qiao-Yan Wen. Quantum algorithm for the Toeplitz systems. arXiv:1608.02184, 2016.

[298] Salvatore Mandra, Gian Giacomo Guerreschi, and Alan Aspuru-Guzik. Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems. arXiv:1512.00859, 2015.

[299] J. Adcock, E. Allen, M. Day, S. Frick, J. Hinchliff, M. Johnson, S. Morley-Short, S. Pallister, A. Price, and S. Stanisic. Advances in quantum machine learning. arXiv:1512.02900, 2015.

[300] Cedric Yen-Yu Lin and Yechao Zhu. Performance of QAOA on typical instances of constraint satisfaction problems with bounded degree. arXiv:1601.01744, 2016.

[301] Dave Wecker, Matthew B. Hastings, and Matthias Troyer. Training a quantum optimizer. arXiv:1605.05370, 2016.

[302] Edward Farhi and Aram W. Harrow. Quantum supremacy through the quantum approximate optimization algorithm. arXiv:1602.07674, 2016.

[303] Thomas G. Wong. Quantum walk search on Johnson graphs. arXiv:1601.04212, 2016.

[304] Jonatan Janmark, David A. Meyer, and Thomas G. Wong. Global symmetry is unnecessary for fast quantum search. Physical Review Letters 112:210502, 2014.arXiv:1403.2228

[305] David A. Meyer and Thomas G. Wong. Connectivity is a poor indicator of fast quantum search. Physical Review Letters 114:110503, 2014.arXiv:1409.5876

[306] Thomas G. Wong. Spatial search by continuous-time quantum walk with multiple marked vertices. Quantum Information Processing 15(4):1411-1443, 2016.arXiv:1501.07071

[307] Anirban Naryan Chowdhury and Rolando D. Somma. Quantum algorithms for Gibbs sampling and hitting-time estimation. arXiv:1603.02940, 2016.

[308] Edward Farhi, Shelby Kimmel, and Kristan Temme. A quantum version of Schoning’s algorithm applied to quantum 2-SAT. arXiv:1603.06985, 2016.

[309] Iordanis Kerenidis and Anupam Prakash. Quantum recommendation systems. arXiv:1603.08675, 2016.

[310] Markus Reiher, Nathan Wiebe, Krysta M. Svore, Dave Wecker, and Matthias Troyer. Elucidating reaction mechanisms on quantum computers. arXiv:1605.03590, 2016.

[311] Aram W. Harrow and Ashley Montanaro. Sequential measurements, disturbance, and property testing. arXiv:1607.03236, 2016.

[312] Martin Roetteler. Quantum algorithms for abelian difference sets and applications to dihedral hidden subgroups. arXiv:1608.02005, 2016.

[313] Fernando G.S.L. Brandao and Krysta Svore. Quantum speed-ups for semidefinite programming. arXiv:1609.05537, 2016.

[314] Z-C Yang, A. Rahmani, A. Shabani, H. Neven, and C. Chamon. Optimizing variational quantum algorithms using Pontryagins’s minimum principle. arXiv:1607.06473, 2016.

[315] Gilles Brassard, Peter Høyer, and Alain Tapp. Quantum cryptanalysis of hash and claw-free functions. In Proceedings of the 3rd Latin American symposium on Theoretical Informatics (LATIN’98), pg. 163-169, 1998.

[316] Daniel J. Bernstein. Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete? In Proceedings of the 4th Workshop on Special-purpose Hardware for Attacking Cryptographic Systems (SHARCS’09), pg. 105-116, 2009.

[317] Chris Cade, Ashley Montanaro, and Aleksandrs Belovs. Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness. arXiv:1610.00581, 2016.

[318] A. Belovs and B. Reichardt. Span programs and quantum algorithms for st-connectivity and claw detectionIn European Symposium on Algorithms (ESA’12) , pg. 193-204, 2012. arXiv:1203.2603

[319] Titouan Carette, Mathieu Laurière, and Frédéric Magniez. Extended learning graphs for triangle finding. arXiv:1609.07786, 2016.

[320] F. Le Gall and N. Shogo. Quantum algorithm for triangle finding in sparse graphs. In Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC’15), pg. 590-600, 2015.

[321] Or Sattath and Itai AradA constructive quantum Lovász local lemma for commuting projectors. Quantum Information and Computation, 15(11/12)987-996pg, 2015. arXiv:1310.7766

[322] Martin Schwarz, Toby S. Cubitt, and Frank Verstraete. An information-theoretic proof of the constructive commutative quantum Lovász local lemma. arXiv:1311.6474

[323] C. Shoen, E. Solano, F. Verstraete, J. I. Cirac, and M. M. Wolf. Sequential generation of entangled multi-qubit states. Physical Review Letters, 95:110503, 2005.arXiv:quant-ph/0501096

[324] C. Shoen, K. Hammerer, M. M. Wolf, J. I. Cirac, and E. Solano. Sequential generation of matrix-product states in cavity QED. Physical Review A, 75:032311, 2007.arXiv:quant-ph/0612101

[325] Yimin Ge, András Molnár, and J. Ignacio Cirac. Rapid adiabatic preparation of injective PEPS and Gibbs states. Physical Review Letters, 116:080503, 2016.arXiv:1508.00570

[326] Martin Schwarz, Kristan Temme, and Frank Verstraete. Preparing projected entangled pair states on a quantum computer. Physical Review Letters, 108:110502, 2012.arXiv:1104.1410

[327] Martin Schwarz, Toby S. Cubitt, Kristan Temme, Frank Verstraete, and David Perez-Garcia. Preparing topological PEPS on a quantum computer. Physical Review A, 88:032321, 2013.arXiv:1211.4050

[328] M. Schwarz, O. Buerschaper, and J. Eisert. Approximating local observables on projected entangled pair states. arXiv:1606.06301, 2016.

[329] Jean-François Biasse and Fang Song. Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields. Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’16), pg. 893-902, 2016.

[330] Peter Høyer and Mojtaba Komeili. Efficient quantum walk on the grid with multiple marked elements. Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), 42, 2016. arXiv:1612.08958

[331] Peter Wittek. Quantum Machine Learning: what quantum computing means to data mining. Academic Press, 2014.

[332] Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione. An introduction to quantum machine learning. Contemporary Physics, 56(2):172, 2014. arXiv:1409.3097

[333] J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd. Quantum machine learning. arXiv:1611.09347

[334] Esma Aïeur, Gilles Brassard, and Sébastien Gambs. Machine learning in a quantum world. In Advances in Artificial Intelligence: 19th Conference of the Canadian Society for Computational Studies of Intelligence pg. 431-442, Springer, 2006.

[335] Vedran Dunjko, Jacob Taylor, and Hans Briegel. Quantum-enhanced machine learning. Phys. Rev. Lett 117:130501, 2016.

[336] Nathan Wiebe, Ashish Kapoor, and Krysta Svore. Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning. Quantum Information and Computation 15(3/4): 0318-0358, 2015. arXiv:1401.2142

[337] Seokwon Yoo, Jeongho Bang, Changhyoup Lee, and Junhyoug Lee. A quantum speedup in machine learning: finding a N-bit Boolean function for a classification. New Journal of Physics 6(10):103014, 2014.arXiv:1303.6055

[338] Maria Schuld, Ilya Sinayskiy, and Frencesco Petruccione. Prediction by linear regression on a quantum computer. Physical Review A 94:022342, 2016.arXiv:1601.07823

[339] Zhikuan Zhao, Jack K. Fitzsimons, and Joseph F. Fitzsimons. Quantum assisted Gaussian process regression. arXiv:1512.03929

[340] Esma Aïeur, Gilles Brassard, and Sébastien Gambs. Quantum speed-up for unsupervised learning. Machine Learning, 90(2):261-287, 2013.

[341] Nathan Wiebe, Ashish Kapoor, and Krysta Svore. Quantum perceptron models. Advances in Neural Information Processing Systems 29 (NIPS 2016), pg. 3999–4007, 2016.arXiv:1602.04799

[342] G. Paparo, V. Dunjko, A. Makmal, M. Martin-Delgado, and H. Briegel. Quantum speedup for active learning agents. Physical Review X4(3):031002, 2014.arXiv:1401.4997

[343] Daoyi Dong, Chunlin Chen, Hanxiong Li, and Tzyh-Jong Tarn. Quantum reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics- Part B (Cybernetics)38(5):1207, 2008.

[344] Daniel Crawford, Anna Levit, Navid Ghadermarzy, Jaspreet S. Oberoi, and Pooya Ronagh. Reinforcement learning using quantum Boltzmann machines. arXiv:1612.05695, 2016.

[345] Steven H. Adachi and Maxwell P. Henderson. Application of Quantum Annealing to Training of Deep Neural Networks. arXiv:1510.06356, 2015.

[346] M. Benedetti, J. Realpe-Gómez, R. Biswas, and A. Perdomo-Ortiz. Quantum-assisted learning of graphical models with arbitrary pairwise connectivity. arXiv:1609.02542, 2016.

[347] M. Benedetti, J. Realpe-Gómez, R. Biswas, and A. Perdomo-Ortiz. Quantum-assisted learning of graphical models with arbitrary pairwise connectivity. arXiv:1609.02542, 2016.

[348] M. H. Amin, E. Andriyash, J. Rolfe, B. Kulchytskyy, and R. Melko. Quantum Boltzmann machine. arXiv:1601.02036, 2016.

[349] Peter Wittek and Christian Gogolin. Quantum enhanced inference in Markov logic networksScientific Reports7:45672, 2017. arXiv:1611.08104, 2016.

[350] N. H. Bshouty and J. C. Jackson. Learning DNF over the uniform distribution using a quantum example oracle. SIAM Journal on Computing28(3):1136-1153, 1999.

[351] Srinivasan Arunachalam and Ronald de Wolf. A survey of quantum learning theory. arXiv:1701.06806, 2017.

[352] Rocco A. Servedio and Steven J. Gortler. Equivalences and separations between quantum and classical learnability. SIAM Journal on Computing, 33(5):1067-1092, 2017.

[353] Srinivasan Arunachalam and Ronald de Wolf. Optimal quantum sample complexity of learning algorithms. arXiv:1607.00932, 2016.

[354] Alex Monràs, Gael Sentís, and Peter Wittek. Inductive quantum learning: why you are doing it almost right. arXiv:1605.07541, 2016.

[355] A. Bisio, G. Chiribella, G. M. D’Ariano, S. Facchini, and P. Perinotti. Optimal quantum learning of a unitary transformation. Physical Review A 81:032324, 2010.arXiv:0903.0543.

[356] M. Sasaki, A. Carlini, and R. Jozsa. Quantum template matchingPhysical Review A 64:022317, 2001. arXiv:quant-ph/0102020.

[357] Masahide Sasaki and Alberto Carlini. Quantum learning and universal quantum matching machine. Physical Review A 66:022303, 2002.arXiv:quant-ph/0202173.

[358] Esma Aïeur, Gilles Brassard, and Sébastien GambsQuantum clustering algorithmsIn Proceedings of the 24th International Conference on Machine Learning (ICML), pg. 1-8, 2007.

[359] Iordanis Kerenidis and Anupam Prakash. Quantum gradient descent for linear systems and least squares. arXiv:1704.04992, 2017.

[360] Dan Boneh and Mark Zhandry. Quantum-secure message authentication codes. In Proceedings of Eurocrypt, pg. 592-608, 2013.

[361] A. M. Childs, W. van Dam, S-H Hung, and I. E. Shparlinski. Optimal quantum algorithm for polynomial interpolation. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), pg. 16:1-16:13, 2016.arXiv:1509.09271

[362] Volker Strassen. Einige Resultate über Berechnungskomplexität. In Jahresbericht der Deutschen Mathematiker-Vereinigung, 78(1):1-8, 1976/1977.

[363] Stacey Jeffery. Frameworks for Quantum AlgorithmsPhD thesis, U. Waterloo, 2014.

[364] Seiichiro Tani. An improved claw finding algorithm using quantum walkIn Mathematical Foundations of Computer Science (MFCS), pg. 536-547, 2007.arXiv:0708.2584

[365] K. Iwama and A. Kawachi. A new quantum claw-finding algorithm for three functions. New Generation Computing, 21(4):319-327, 2003.

[366] D. J. Bernstein, N. Heninger, P. Lou, and L. Valenta. Post-quantum. RSAIACR e-print 2017/351, 2017.

[367] Francois Fillion-Gourdeau, Steve MacLean, and Raymond Laflamme. Quantum algorithm for the dsolution of the Dirac equation. arXiv:1611.05484, 2016.

[368] Ali Hamed Moosavian and Stephen Jordan. Faster quantum algorithm to simulate Fermionic quantum field theory. arXiv:1711.04006, 2017.

[369] Pedro C.S. Costa, Stephen Jordan, and Aaron Ostrander. Quantum algorithm for simulating the wave equation. arXiv:1711.05394, 2017.

[370] Jeffrey Yepez. Highly covariant quantum lattice gas model of the Dirac equation. arXiv:1106.0739, 2011.

[371] Jeffrey Yepez. Quantum lattice gas model of Dirac particles in 1+1 dimensions. arXiv:1307.3595, 2013.

[372] Bruce M. Boghosian and Washington Taylor. Simulating quantum mechanics on a quantum computer. Physica D 120:30-42, 1998. [arXiv:quant-ph/9701019]

[373] Yimin Ge, Jordi Tura, and J. Ignacio Cirac. Faster ground state preparation and high-precision ground energy estimation on a quantum computer. arXiv:1712.03193, 2017.

[374] Renato Portugal. Element distinctness revisited. arXiv:1711.11336, 2017.

[375] Kanav Setia and James D. Whitfield. Bravyi-Kitaev superfast simulation of fermions on a quantum computer. arXiv:1712.00446, 2017.

[376] Richard Cleve and Chunhao Wang. Efficient quantum algorithms for simulating Lindblad evolution. arXiv:1612.09512, 2016.

[377] M. Kliesch, T. Barthel, C. Gogolin, M. Kastoryano, and J. Eisert. Dissipative quantum Church-Turing theorem. Physical Review Letters 107(12):120501, 2011.[arXiv:1105.3986]

[378] A. M. Childs and T. Li. Efficient simulation of sparse Markovian quantum dynamics. arXiv:1611.05543, 2016.

[379] R. Di Candia, J. S. Pedernales, A. del Campo, E. Solano, and J. Casanova. Quantum simulation of dissipative processes without reservoir engineering. Scientific Reports 5:9981, 2015.

[380] R. Babbush, D. Berry, M. Kieferová, G. H. Low, Y. Sanders, A. Sherer, and N. Wiebe. Improved techniques for preparing eigenstates of Fermionic Hamiltonians. arXiv:1711.10460, 2017.

[381] D. Poulin，A。Kitaev，DS Steiger，MB Hasting和M. Troyer。光谱特性的快速量子算法。arXiv：1711.11025，2017年。

[382] Low Guang Hao和Isaac Chuang。哈密​​顿模拟bt量子化。arXiv：1610.06546，2016。

[383] FGSLBrandão，A。Kalev，T。Li，CY-Y。Lin，KM Svore和X.Wu。半定规划的指数式量子加速及其在量子学习中的应用。arXiv：1710.02581，2017年。

[384] M.Ekerå和J.Håstad。用于计算短离散对数和分解RSA的量子算法。PQCrypto 2017的Integers Proceedings，第16页。347-363。（LNCS卷10346），2017.

[385] M.Ekerå。在量子算法的后处理中，计算短离散对数I。ACR ePrint存档报告2017/1122，2017.

[386] DJ Bernstein，J.-F. Biasse和M. Mosca。一种低资源量子分解算法。PQCrypto 2017的会议记录，第 330-346（LNCS第10346卷），2017年。

[387]陈建新，安德鲁·柴尔德斯和洪世汉。多元多项式插值的量子算法。皇家学会学报A，474：20170480，2017.arXiv：1701.03990

[388]丽莎· 海尔斯和肖恩·哈尔格伦。一种改进的量子傅立叶变换算法及其应用。在《 FOCS 2000会议论文集》中。515-525。

[389] Igor Shparlinski和Arne Winterh的量子周期重建近似序列。信息处理快报，103：211-215，2007。

[390]亚历山大·罗素（Alexander Russell）和伊戈尔·E·什帕林斯基（Igor E. Shparlinski）通过字符评估重建经典和量子函数。Journal of Complexity，20：404-422，2004。

[391]肖恩·哈格伦，亚历山大·罗素和伊戈尔·谢泼林斯基。量子噪声有理函数重构。《 COCOON 2005》论文集，第5页。420-429。

[392] G. Ivanyos，M。Karpinski，M。Santha，N。Saxena和I. Shparlinski多项式插值和从有限域上的高阶幂进行的身份检验。Algorithmica，80：560-575，2017年。